7.3.2 平衡二叉树

教材导航 · 第7章

原书定位

印刷页P287起,对应PDF第299页。下文为目视整理的知识提要;完整内容见原书对照。

AVL 是任一结点左右子树高度差绝对值不超过 1 的 BST。平衡因子定义为左高减右高,取值为 −1,0,1-1,0,1,空树也满足平衡条件。

平衡约束须对每个结点成立;只检查根不够。AVL 不要求完全或左右结点数接近,但可保证树高 O(log⁡n)O(\log n)。

AVL 平衡因子示例

AVL 平衡因子示例,原书P287。

下级知识点

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P287,PDF第299页