知识卡片

普通读书笔记卡 · 5654.d.1.e.4.r · 生成模型:未记录

平衡因子先固定高度差方向

理解等级:中级

AVL要求每个节点左右子树高度差绝对值至多1,以局部约束限制整树高度。因子可选不同符号约定,但定义、图、常量和旋转更新必须统一。

本书文字写“右高度减左高度”,却又规定左重为+1、右重为−1;02872中左重节点标+1,02876常量AVL_LFT_HEAVY=1、AVL_RGT_HEAVY=−1。因此解释本实现应采用“左高度减右高度”,不能把文字反方向代入。

插入后沿路径更新因子,若某祖先出现±2就需要局部旋转恢复约束。这里维护的是相邻子树高度差,不要求每一层填满,也不保证每次插入都必须旋转。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      结点的平衡因子。结点的平衡因子是它的右子树高度减去它的左子树高度的结果(见图9-9)。当插入结点时,AVL树需要自我调整,使得所有结点的平衡因子保持为+1、-1或0。当子树的根结点平衡因子为+1时,它是左倾斜的(left-heavy)。当子树的根结点平衡因子为-1时,它是右倾斜的(right-hea

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉搜索树的实现与分析》(spine1299;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1266.html;u160-ch09-019)。 - 结论依据:160全部定义及02872整图实读,与161/02876三常量、02879–02880旋转更新核对统一符号;原文正负矛盾已明确处理。 - 原始内容:结点的平衡因子。结点的平衡因子是它的右子树高度减去它的左子树高度的结果(见图9-9)。当插入结点时,AVL树需要自我调整,使得所有结点的平衡因子保持为+1、-1或0。当子树的根结点平衡因子为+1时,它是左倾斜的(left-heavy)。当子树的根结点平衡因子为-1时,它是右倾斜的(right-hea