知识卡片

普通读书笔记卡 · 5654.d.1.e.4.t · 生成模型:未记录

双旋转提升内侧孙节点

理解等级:中级

LR是新项落在A左孩子L的右子树;将内侧孙节点G=L.right提升为局部根,L与A分别成为它左右孩子,G原左右子树分别交回L.right与A.left。RL为右孩子的左侧情形,对称重接。

因子采用本实现左高减右高约定,旋转前G的值决定旧根/孩子调整:

G旧因子 LR后A,L RL后A,R
+1 −1,0 0,−1
0 0,0 0,0
−1 0,+1 +1,0

G最终均为0。02874–02875展示LR链接与三种因子情况;RL文字把若干right误写left,实际02880代码按R更新,上表采用实际对称关系。保持键序与正确重接每份子树,比背函数名更重要。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      LR旋转 如图9-11所示,当x位于A的左子树的右子树上时,执行LR旋转。设left是A的左子结点,并设A的子孙结点grandchild为left的右子结点。要执行LR旋转,将left的右子结点指向grandchild的左子结点,grandchild的左子结点指向left,A的左子结点指向grand

    参考来源

    - 位置:《算法精解:C语言描述》第9章《AVL树的旋转》(spine1299;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1266.html;u161-ch09-021)。 - 结论依据:161完整LR/RL全部段落及02874六步图、02875三组因子图、02879–02880完整双旋代码逐项实读;表是原图/代码的整理,未测试。 - 原始内容:LR旋转 如图9-11所示,当x位于A的左子树的右子树上时,执行LR旋转。设left是A的左子结点,并设A的子孙结点grandchild为left的右子结点。要执行LR旋转,将left的右子结点指向grandchild的左子结点,grandchild的左子结点指向left,A的左子结点指向grand