知识卡片
平衡因子先固定高度差方向
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