知识卡片
插入回归只更新祖先路径
AVL插入先按比较沿单条路径定位,新增节点后在递归返回时更新经过的祖先。这里不遍历同一层的全部节点,正文关于“当前层所有节点”的表述不符合实际递归路径。
本实现balanced指针用于控制高度变化是否还需向上传递:新插入使子树增高时为0;某祖先从偏斜变为平衡,或完成一次恢复高度的旋转后置1,停止继续调整上层。它不是指“0就整树未满足AVL、1就已证明所有业务成功”的通用状态。
左侧新增时,原左重可能需LL/LR旋转,原平衡改左重并继续传播,原右重则改平衡并停止;右侧对称。隐藏位置恢复不改结构,高度未增,所以无需重新平衡。每步局部常数操作加上受限树高给出O(log N),N计结构节点包括隐藏项,不能把原文1.5klog N当任意输入精确耗时。
165的02878图依次27/45/34触发RL,加入20/11触发LL,再加59/10/25/29/30触发LR,重接后根为27;图是插入旋转说明,不是删除触发旋转的证明。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
递归的回归过程中完成。如果在处理的过程中有任何结点的平衡因子的绝对值为2,都需要执行一次旋转。 从检查是否将结点插入空树开始。如果是这种情况,简单地将结点设为根结点,并设它的平衡因子为AVL_BALANCED。否则,将待插入结点的数据与当前结点的数据相比较,以此来判断需要往哪个方向移动(左子树还是右
- · 查看原书依据
将结点插入AVL树中 从AVL树中移除结点的过程分析同插入结点一样,因此bistree_remove的时间复杂度为O(lg n)。
参考来源
- 位置:《算法精解:C语言描述》第9章《bistree_insert》(spine1302;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1269.html;u164-ch09-023)。
- 结论依据:164完整控制说明及02882–02884完整insert两侧递归/switch/隐藏恢复分支实读;02878示例三次旋转已读,明确只走祖先路径与balanced实际职责。
- 原始内容:递归的回归过程中完成。如果在处理的过程中有任何结点的平衡因子的绝对值为2,都需要执行一次旋转。 从检查是否将结点插入空树开始。如果是这种情况,简单地将结点设为根结点,并设它的平衡因子为AVL_BALANCED。否则,将待插入结点的数据与当前结点的数据相比较,以此来判断需要往哪个方向移动(左子树还是右
- 位置:《算法精解:C语言描述》第9章《bistree_remove》(spine1303;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1270.html;u165-ch09-023)。
- 结论依据:165的02878图依次27/45/34触发RL,加入20/11触发LL,再加59/10/25/29/30触发LR,重接后根为27;图是插入旋转说明,不是删除触发旋转的证明。
- 原始内容:将结点插入AVL树中 从AVL树中移除结点的过程分析同插入结点一样,因此bistree_remove的时间复杂度为O(lg n)。