知识卡片
旋转保持中序并改变高度
旋转通过局部重接父子关系,让较高一侧上升。右旋时把左孩子升为根,它原来的右子树交给旧根的左侧,再让旧根成为新根右孩子;左旋是对称过程。
中间子树必须正确重新挂接,才能保持中序次序。先更新下降的旧根高度,再更新上升的新根,并把新子树根返回给上层接住;只换两个指针而丢中间子树会破坏数据。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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