知识卡片
双旋转提升内侧孙节点
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