AVL树

✍ dations ◷ 2025-06-08 11:29:33 #树结构

在计算机科学中,AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O ( log n ) {\displaystyle O(\log {n})} 个节点被旋转,而每次AVL旋转耗费固定的时间,所以删除处理在整体上耗费O(log ) 时间。

可以像普通二叉查找树一样的进行,所以耗费O(log )时间,因为AVL树总是保持平衡的。不需要特殊的准备,树的结构不会由于查找而改变。(这是与伸展树搜索相对立的,它会因为搜索而变更树结构。)

假设平衡因子是左子树的高度减去右子树的高度所得到的值,又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a(即a是离插入点最近,且平衡因子绝对值超过1的祖先节点),则失去平衡后进行的规律可归纳为下列四种情况:

在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下:

AVL树的调平(Erlang的实现)

 1 balance(null) -> null; 2 balance({null, _, null}=Tree) -> Tree; 3 balance({Left, Value, Right}=Tree) -> 4 	Diff = count(Left)-count(Right), 5 	if (Diff < 2) and (Diff > -2)	->	{balance(Left), Value, balance(Right)}; 6 	   (Diff > 1)				->	balance(rotate_right(Tree)); 7 	   (Diff< -1)				->	balance(rotate_left(Tree)); 8 	   true					->	exit('This is impossible!') 9 	end.10 11 rotate_right({Left, Value, Right}) ->12 	merge_max(Left, {null, Value, Right}).13 14 rotate_left({Left, Value, Right}) ->15 	merge_min(Right, {Left, Value, null}).16 17 merge_min({null, Value, Right}, Tree2) ->18 	{Tree2, Value, Right};19 merge_min({Left, _, _}, Tree2) ->20 	merge_min(Left, Tree2).21 22 merge_max({Left , Value, null}, Tree2) ->23 	{Left, Value, Tree2};24 merge_max({_, _, Right}, Tree2) ->25 	merge_max(Right, Tree2).

AVL节点数计算

高度为h的AVL树,总节点数N最多 2 h 1 {\displaystyle 2^{h}-1} ; 最少节点数 N h {\displaystyle N_{h}} 如以斐波那契数列可以用数学归纳法证明:
N h {\displaystyle N_{h}} = F h + 2 {\displaystyle F_{h+2}} - 1 ( F h + 2 {\displaystyle F_{h+2}} 是斐波那契数列的第h+2项,根据斐波那契多项式得来)。
即:
N 0 {\displaystyle N_{0}} = 0 (表示AVL Tree高度为0的节点总数)
N 1 {\displaystyle N_{1}} = 1 (表示AVL Tree高度为1的节点总数)
N 2 {\displaystyle N_{2}} = 2 (表示AVL Tree高度为2的节点总数)
N h {\displaystyle N_{h}} = N h 1 {\displaystyle N_{h-1}} + N h 2 {\displaystyle N_{h-2}} + 1 (表示AVL Tree高度为h的节点总数)
换句话说,当节点数为N时,高度h最多为 l o g Φ ( 5 ( N + 1 ) ) 2 {\displaystyle log_{\Phi }({\sqrt {5}}*(N+1))-2}

相关

  • 泰勒斯米利都的泰勒斯(希腊语:Θαλῆς ὁ Μιλήσιος,公元前624年-公元前546年),常被称为泰勒斯(希腊语:Θαλῆς,Thalēs,英语:Thales,/ˈθeɪliːz/),是古希腊古风时期的自然哲学
  • 法利赛人法利赛人(.mw-parser-output .Polytonic{font-family:"SBL BibLit","SBL Greek","EB Garamond","EB Garamond 12","Foulis Greek",Cardo,"Gentium Plus",Gentium,"Theano Di
  • 秀姑峦溪秀姑峦溪(阿美语:Siwkolan a tarawadaw)位于台湾东南部,属于中央管河川,以泛舟活动知名。秀姑峦溪本身发源于花莲与台东两县之间的仑天山南侧,但整个水系的最远源流则为其最长支流
  • 526年安提阿地震526年安提阿地震是一场发生在公元526年拜占庭帝国安提阿(当时称为狄奥波里斯,拉丁语:Theopolis,现归叙利亚和土耳其管辖)的地震 。本地震发生于该年5月下旬,5月20日至29日之间的某
  • 五星上将五星上将(英语:General of the Army/Five-Star General),相当于其他一些国家的元帅,也是美国第二高的军阶和目前可以获得的最高军衔。历史上只有9人拥有此军衔。该军衔仅在战时授
  • 朱之锡朱之锡(1624年1月26日-1666年3月27日),字孟九,号梅麓,浙江义乌陇头朱山头下人。清初治河名臣。明天启二年(1622年)十二月初七日生于北京,父朱三凤经商致富,后家道中落,母沈氏“脱簪珥形
  • 长发姑娘《长发姑娘》(德语:Rapunzel),又译《莴苣姑娘》、《长发公主》,是格林兄弟搜集的德国童话,收录于1812年所出版的《儿童与家庭童话集》。是广为人知的童话故事,这个童话的场景也被许
  • 独派独派可以指:其他国家也有类似情形存在的地区也会称该支持独立的派系为“独派”。
  • 火山及琉球群岛东南亚地区:缅甸:西南太平洋地区:北美地区:日本:满洲地区:硫磺及琉球群岛战事发生在1945年1月至6月间,是盟军与日本皇军在太平洋战场上爆发的一系列战役。战事是以火山列岛及琉球群
  • 安息年安息年(希伯来语:.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram Tsova","Taamey A