知识卡片

普通读书笔记卡 · 5654.d.1.e.1.a.1.a

旋转保持中序并改变高度

理解等级:中级

旋转通过局部重接父子关系,让较高一侧上升。右旋时把左孩子升为根,它原来的右子树交给旧根的左侧,再让旧根成为新根右孩子;左旋是对称过程。

中间子树必须正确重新挂接,才能保持中序次序。先更新下降的旧根高度,再更新上升的新根,并把新子树根返回给上层接住;只换两个指针而丢中间子树会破坏数据。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      将 grand_child 作为node 的左子节点。 图7‑27 有grand_child 的右旋操作 “向右旋转”是一种形象化的说法,实际上需要通过修改节点指针来实现,代码如下所示: // === File: avl

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[9443,9553)) - 结论依据:实际右旋/中间子树图与左右旋代码及高度更新顺序支持。 - 原始内容:将 grand_child 作为node 的左子节点。 图7‑27 有grand_child 的右旋操作 “向右旋转”是一种形象化的说法,实际上需要通过修改节点指针来实现,代码如下所示: // === File: avl