知识卡片
树更新返回新的子树根
AVL递归插删完成一层局部改动后,先重算该层高度,再选择旋转,并把可能改变的新根返回。上层把它接回对应子方向,顶层则更新整棵树根。
只在底部旋转而不接回新根,会使入口仍指旧结构;只维护插入而忽略删除,也会在后续失衡。判断成功应看搜索次序、高度记录与平衡约束是否同时成立,而不是仅看目标键消失或出现。
树章问答明确:旋转函数只返回新的局部根,维护它与原父节点的连接属于调用方职责。内部高度重算应随着插删流程执行,不宜让使用方任意调用以绕开结构维护。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
需要从底至顶执行旋转操作,使所有失衡节点恢复平衡。 代码如下所示: // === File: avl_tree.go === /* 删除节点 */ func (t *aVLTree) remove(val int) {
- · 查看原书依据
子树的根节点和其父节点的连接是在该函数返回后完成的,不 属于右旋操作的维护范围。 Q:在C++ 中,函数被划分到private public 中,这方面有什么考量吗?为什么要将height() 函数和 updateHei
参考来源
- 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[12366,12475))
- 结论依据:实际insertHelper/removeHelper返回与t.root赋值支持路径回溯维护。
- 原始内容:需要从底至顶执行旋转操作,使所有失衡节点恢复平衡。 代码如下所示: // === File: avl_tree.go === /* 删除节点 */ func (t *aVLTree) remove(val int) {
补充原书证据:spine 3 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;归一字符[14711,14821)。
- 结论依据:实际问答补充方法职责与内部维护边界。
- 原始内容:子树的根节点和其父节点的连接是在该函数返回后完成的,不 属于右旋操作的维护范围。 Q:在C++ 中,函数被划分到private public 中,这方面有什么考量吗?为什么要将height() 函数和 updateHei