7.3.2.3 AVL 的查找与高度界
原书定位
印刷页P290起,对应PDF第302页。下文为目视整理的知识提要;完整内容见原书对照。
查找与普通 BST 相同。令 为高度 的 AVL 最少结点数,根在第 1 层、空树高 0:
依次为 ,可据此求给定结点数的最大高度。最大结点数为 。最少结点数呈斐波那契增长,因此查找、插入、删除最坏 。

给定高度下结点数最少的 AVL 树,原书P291。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P290起,对应PDF第302页。下文为目视整理的知识提要;完整内容见原书对照。
查找与普通 BST 相同。令 为高度 的 AVL 最少结点数,根在第 1 层、空树高 0:
依次为 ,可据此求给定结点数的最大高度。最大结点数为 。最少结点数呈斐波那契增长,因此查找、插入、删除最坏 。

给定高度下结点数最少的 AVL 树,原书P291。

