知识卡片

普通读书笔记卡 · 5654.d.1.e.1.a.1.a.2

树更新返回新的子树根

理解等级:中级

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