AVL樹

AVL 樹（Adelson-Velsky and Landis Tree）是電腦科學中上早被發明的自平衡二箍搜揣樹仔。佇咧 AVL 樹中，任一節點對應的兩欉樹仔上大欉的差一，所以伊嘛予人號做懸度平衡樹。走揣、插入去攏共刪除佇平均佮上歹的情形下的時間複雜度攏是 $ O ( \ log { n } ) $。增加佮刪除元素的操作則可能需要藉過一改抑是真濟改樹仔旋轉，以實現樹仔的重新平衡。AVL 樹仔著名伊的發明者 G . M . Adelson-Velsky 和 Evgenii Landis，𪜶佇一九六二年的論文《An algorithm for the organization of information》中公開了這資料結構。

節點的平衡因為是伊的倒子樹的懸度減去伊的正子樹的懸度（有時倒反）。 帶有平衡因為一、零抑是鋪一的節點予人認為是平衡的。帶有平衡因為抹第二抑是二的節點予人認為是無平衡的，並且需要重新平衡這个樹仔。平衡因為會當直接儉佇每一个節點內底，抑是自可能儲存佇咧節點中的子樹仔高度計算出來。

操作

AVL 樹仔的基本操作一般牽涉著運作仝佇無平衡的二箍揣樹仔所運作的仝款的演算法。但是欲進行預先抑是隨後做一遍抑是濟遍所謂的 " AVL 旋轉 "。

以下圖表以四列表示四種情形，逐家表示這種情況下欲做的操作。佇左佮正爿的狀況之下，只需要進行一擺旋轉操作；佇彼左右佮彼左右的狀況之下，需要進行兩遍旋轉操作。

刪除

對 AVL 樹中刪除，會當通過共愛刪除的節點向下旋轉做一个葉仔節點，紲落直接徙掉這个葉仔節點來完成。因為佇旋轉做葉仔節點期間上濟有 log _ n _ 個節點予人旋轉，而且逐擺 AVL 旋轉了固定的時間，所以刪除處理咧整體費 O ( log _ n _ ) 時間。

搜揣

會當親像普通二箍搜揣樹仔仝款的進行，所以了 O ( log _ n _ ) 時間，因為乎 AVL 樹總是保持平衡的。無需要特殊的準備，樹的結構袂因為走揣來改變。（這是佮伸展樹仔搜揣相對立的，伊會因為搜揣來變更樹結構。）

實現描述

假做平衡因為是倒囝樹的懸度減去正子樹的懸度所得著的值，又閣假使用因為佇兩元排序樹頂插入節點無去平衡的上細囝樹根節點的指標準做 a（即 a 是離插入點最近，而且平衡因為絕對值超過一的祖先節點）， 則失去平衡了後進行的規律會當歸納做下列四種情形：

一 . 單向正旋平衡的處理 LL：因為佇咧 \ * a 的倒手樹根節點的倒手樹仔頂插入節點，\ * a 的平衡因為一增加到二，致使以 \ * a 為根的子樹失去平衡，需要進行按呢一擺踅踅操作； 二 . 單向倒旋平衡來處理 RR：因為佇咧 \ * a 的正手樹根節點的正手樹頂插入節點，\ * a 的平衡因為-一變做是-二，致使以 \ * a 為根的子樹失去平衡，需要進行一擺倒手旋轉操作； 三 . 雙爿踅（先倒後正）平衡的處理 LR：因為佇咧 \ * a 的倒手樹根節點的正手樹仔頂插入節點，\ * a 的平衡因為一增加到二，致使以 \ * a 為根的子樹失去平衡，需要進行兩回回回（先倒旋後正旋）操作。 四 . 雙爿踅（先正後倒）平衡的處理 RL：因為佇咧 \ * a 的正手樹根節點的倒手樹仔頂插入節點，\ * a 的平衡因為-一變做是-二，致使以 \ * a 為根的子樹失去平衡，需要進行兩回回回（先正旋後倒旋）操作。

佇咧平衡的二箍排做樹 BBST ( Balancing Binary Search Tree ) 頂頭插一个新的資料的元素 e 遞迴演算法會當描述如下：

一 . 若是 BBST 為空樹，則插一个資料的元素為 e 的新節點做 BBST 的根節點，樹仔的深度增一； 二 . 若是 e 的關鍵字佮 BBST 的根節點的關鍵字相等，是無進行的； 三 . 若是 e 的關鍵字小於 BBST 的根節點的關鍵字，而且佇咧 BBST 的倒子樹內底是無存在的 e 有仝款關鍵字的節點，則將 e 插入去 BBST 的倒子樹頂，並且做插入了後的倒子樹深度增加（+ 一）時，分別就落列無仝款狀況處理之： 一 . BBST 的根節點的平衡因為-一（正子樹的深度大佇倒子樹的深度，是共根節點的平衡因為更改做零，BBST 的深度不變； 二 . BBST 的根節點的平衡因為零（倒、正子樹的深度相等）： 是共根節點的平衡因為更改做一，BBST 的深度增一； 三 . BBST 的根節點的平衡因為一（倒爿樹仔的深度大佇正子樹仔的深度）： 則若 BBST 的倒爿樹根節點的平衡因為一：愛開始進行單向正旋平衡處理，並且佇咧正手旋處理了後，共根節點佮其正手樹根節點的平衡因為閣較改做零，樹仔的深度無變； 四 . 若是 e 的關鍵字就較大 BBST 的根節點的關鍵字，而且佇咧 BBST 的正子樹中不存在和 e 有仝款關鍵字的節點，則將 e 插入去 BBST 的正子樹頂，並且做插入了的正子樹深度增加（+ 一）時，分別就無仝款狀況處理之。

AVL 樹仔的調平（Erlang 的實現）

AVL 節點數計算

懸度為 h 的 AVL 樹，總節點數 N 上濟 $ 二 ^ { h + 一 } 影一 $； 上少節點數 $ N _ { h } $ 如以斐波那契數列會當用數學歸納法證明： $ N _ { h } $=$ F _ { h + 二 } $-一 ( $ F _ { h + 二 } $ 是斐波彼契數列的第 h + 二項，根據斐波彼契多項式來矣 )。 即 : $ N _ { 零 } $=零 ( 表示 AVL Tree 懸度為零的節點總數 ) $ N _ { 一 } $=一 ( 表示 AVL Tree 懸度為一的點總數 ) $ N _ { 二 } $=二 ( 表示 AVL Tree 懸度為二的點字總數 ) $ N _ { h } $=$ N _ { h 影一 } $ + $ N _ { h 鋪二 } $ + 一 ( 表示 AVL Tree 懸度為 h 的點總數 ) 嘛會使講，做節點數為 N 時，懸度 h 上濟為 $ log _ { \ Phi } ( { \ sqrt { 五 } } * ( N + 一 ) ) 鋪二 $。

參見

• 樹旋轉
• 伸展樹
• 紅烏樹
• B 樹

參照

• G . Adelson-Velskii and E . M . Landis , " An algorithm for the organization of information . " _ Doklady Akademii Nauk SSSR _ , 一百四十六 : 兩百六十三–兩百六十六 , 一千九百六十二（Russian）. English translation by Myron J . Ricci in _ Soviet Math . Doklady _ , 三 : 千二百五十九–千二百六十三 , 一千九百六十二 .

外部連結

• Description from the Dictionary of Algorithms and Data Structures
• AVL Tree Traversal
• Linked AVL tree
• C + + AVL Tree Template and C AVL TREE " Generic Package " by Walt Karas
• A Visual Basic AVL Tree Container Class by Jim Harris
• AVL Trees : Tutorial and C + + Implementation by Brad Appleton
• Ulm's Oberon Library : AVLTrees
• The AVL TREE Data Type
• CNAVLTree Class Reference
• GNU libavl
• AVL-trees-balanced binary trees by Alex Konshin
• Simulation of AVL Trees
• AVL tree applet
• Simulation of AVL Trees ( DYNAMIC )
• AVL , Splay and Red / Black Applet