7.3.2.3 AVL 的查找与高度界

教材导航 · 第7章

原书定位

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

查找与普通 BST 相同。令 NhN_h 为高度 hh 的 AVL 最少结点数,根在第 1 层、空树高 0:

N0=0,N1=1,Nh=1+Nh−1+Nh−2N_0=0,\quad N_1=1,\quad N_h=1+N_{h-1}+N_{h-2}

依次为 0,1,2,4,7,12,20,33,…0,1,2,4,7,12,20,33,\ldots,可据此求给定结点数的最大高度。最大结点数为 2h−12^h-1。最少结点数呈斐波那契增长,因此查找、插入、删除最坏 O(log⁡n)O(\log n)。

给定高度下结点数最少的 AVL 树

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

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P290,PDF第302页

原书对照,原书P291,PDF第303页