知识卡片
单旋转保持中序次序
设A是插入路径上最近的失衡祖先,按路径区分情形:新节点落在A左孩子的左子树为LL,落在右孩子的右子树为RR。LL把左孩子L提升:A.left改接L.right,L.right接A,原来指向A的位置改指L;RR对称地提升右孩子。
这重排局部根,不改变中序键次序,中间子树必须转接而不能丢掉。插入导致的这两种情形旋转后,旧根和被提升孩子因子均恢复0。规则不能直接套到所有删除旋转,后者未在此实现。
书中函数rotate_left处理左侧失衡的LL/LR,LL几何上实际是向右转;rotate_right处理RR/RL,名称按失衡侧而非通常几何方向。RR文字中的left应为right,按对称链接和实际代码理解。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
LL旋转 如图9-10所示,当x位于A的左子树的左子树上时,执行LL旋转。设left为A的左子树,要执行LL旋转,将A的左指针指向left的右子结点,left的右指针指向A,将原来指向A的指针改为指向left。旋转过后,将A和left的平衡因子都改为0。所有其他结点的平衡因子没有发生改变。 图 9-
参考来源
- 位置:《算法精解:C语言描述》第9章《AVL树的旋转》(spine1299;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1266.html;u161-ch09-020)。
- 结论依据:161全部LL/RR说明、02873四步图及02879–02880完整单旋代码实读,转接中间子树和函数命名均按实际控制流解释。
- 原始内容:LL旋转 如图9-10所示,当x位于A的左子树的左子树上时,执行LL旋转。设left为A的左子树,要执行LL旋转,将A的左指针指向left的右子结点,left的右指针指向A,将原来指向A的指针改为指向left。旋转过后,将A和left的平衡因子都改为0。所有其他结点的平衡因子没有发生改变。 图 9-