7.3.2 平衡二叉树
原书定位
印刷页P287起,对应PDF第299页。下文为目视整理的知识提要;完整内容见原书对照。
AVL 是任一结点左右子树高度差绝对值不超过 1 的 BST。平衡因子定义为左高减右高,取值为 ,空树也满足平衡条件。
平衡约束须对每个结点成立;只检查根不够。AVL 不要求完全或左右结点数接近,但可保证树高 。

AVL 平衡因子示例,原书P287。
下级知识点
对应练习
关联知识
- 5.2.1.1 几种特殊的二叉树
- 7.3 树形查找
- 7.3.1 二叉排序树的定义
- 7.3.2.1 AVL 的插入与平衡旋转
- 7.3.2.2 AVL 的删除
- 7.3.2.3 AVL 的查找与高度界
- 7.3.3 红黑树
- 8.4.2 堆的定义
原书对照
展开原书对照截图
