在計算機科學(xué)中，AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點對應(yīng)的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復(fù)雜度都是 {displaystyle O(log {n})} O(log{n})。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)，以實現(xiàn)樹的重新平衡。AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky和Evgenii Landis，他們在1962年的論文《An algorithm for the organization of information》中公開了這一數(shù)據(jù)結(jié)構(gòu)。

理論

實現(xiàn)AVL樹的要點為：每次新增/刪除節(jié)點后?判斷平衡性?然后通過?調(diào)整?使整棵樹重新平衡

判斷平衡性：每次新增/刪除節(jié)點后，刷新受到影響的節(jié)點的高度，即可通過任一節(jié)點的左右子樹高度差判斷其平衡性

調(diào)整：通過對部分節(jié)點的父子關(guān)系的改變使樹重新平衡

進群：697699179可以獲取Java各類入門學(xué)習(xí)資料！

這是我的微信公眾號【編程study】各位大佬有空可以關(guān)注下，每天更新Java學(xué)習(xí)方法，感謝！

學(xué)習(xí)中遇到問題有不明白的地方，推薦加小編Java學(xué)習(xí)群：697699179內(nèi)有視頻教程 ，直播課程 ，等學(xué)習(xí)資料，期待你的加入

實現(xiàn)

基本結(jié)構(gòu)

publicclassTree<TextendsComparable<T>>{privatestaticfinalintMAX_HEIGHT_DIFFERENCE=1;privateNode root;classNode<KT>{KTkey;Node left;Node right;? ? ? ? int height =1;? ? ? ? publicNode(KTkey,Node left,Node right) {this.key = key;this.left = left;this.right = right;? ? ? ? }? ? }}

插入（insert）

四種不平衡范型

對于任意一次?插入所造成的?不平衡，都可以簡化為下述四種范型之一：

下面四張圖中的數(shù)字僅代表節(jié)點序號，為了后文方便展示調(diào)整過程

4、5、6、7號節(jié)點代表了四棵高度可以使不平衡成立的子樹（遵循插入的規(guī)則）

LL型

LR型

RR型

RL型

總結(jié)得到判斷范型的方法為：不平衡的節(jié)點（節(jié)點1）通往高度最大的子樹的葉子節(jié)點時所途經(jīng)的前兩個節(jié)點（節(jié)點2、節(jié)點3）的方向

調(diào)整方法

LL型

5號節(jié)點?作為?1號節(jié)點?的左孩子

1號節(jié)點?作為?2號節(jié)點?的右孩子

例子（例子中的數(shù)字代表節(jié)點的值）：

插入?節(jié)點5?后造成?節(jié)點9?不平衡，其范型為?LL型?，按照固定步驟調(diào)整后全局重新達到平衡

LR型

6號節(jié)點?作為?2號節(jié)點?的右孩子

7號節(jié)點?作為?1號節(jié)點?的左孩子

2號節(jié)點?作為?3號節(jié)點?的左孩子

1號節(jié)點?作為?3號節(jié)點?的右孩子

例子（例子中的數(shù)字代表節(jié)點的值）：

插入?節(jié)點8.5?后造成?節(jié)點9?不平衡，其范型為?LR型?，按照固定步驟調(diào)整后全局重新達到平衡

RR型

5號節(jié)點?作為?1號節(jié)點?的右孩子

1號節(jié)點?作為?2號節(jié)點?的左孩子

例子（例子中的數(shù)字代表節(jié)點的值）：

插入?節(jié)點10.5?后造成?節(jié)點7?不平衡，其范型為?RR型?，按照固定步驟調(diào)整后全局重新達到平衡

RL型

7號節(jié)點?作為?2號節(jié)點?的左孩子

6號節(jié)點?作為?1號節(jié)點?的右孩子

2號節(jié)點?作為?3號節(jié)點?的右孩子

1號節(jié)點?作為?3號節(jié)點?的左孩子

例子（例子中的數(shù)字代表節(jié)點的值）：

插入?節(jié)點7.5?后造成?節(jié)點7?不平衡，其范型為?RL型?，按照固定步驟調(diào)整后全局重新達到平衡

代碼實現(xiàn)

publicvoid insert(Tkey) {if(key == null) {thrownewNullPointerException();? ? }? ? root = insert(root, key);}privateNode insert(Node node,Tkey) {if(node == null) {returnnewNode<>(key, null, null);? ? }? ? int cmp = key.compareTo(node.key);if(cmp ==0) {returnnode;? ? }if(cmp <0) {? ? ? ? node.left= insert(node.left, key);? ? }else{? ? ? ? node.right= insert(node.right, key);? ? }if(Math.abs(height(node.left) - height(node.right)) >MAX_HEIGHT_DIFFERENCE) {? ? ? ? node = balance(node);? ? }? ? refreshHeight(node);returnnode;}privateint height(Node node) {if(node == null) {return0;? ? }returnnode.height;}privatevoid refreshHeight(Node node) {? ? node.height =Math.max(height(node.left), height(node.right)) +1;}/**

* 此方法中的node, node1, node2分別代表上文范型中的1、2、3號節(jié)點

*/privateNode balance(Node node) {Node node1, node2;// llif(height(node.left) > height(node.right) &&? ? ? ? ? ? height(node.left.left) > height(node.left.right)) {? ? ? ? node1 = node.left;? ? ? ? node.left= node1.right;? ? ? ? node1.right= node;? ? ? ? refreshHeight(node);returnnode1;? ? }// lrif(height(node.left) > height(node.right) &&? ? ? ? ? ? height(node.left.right) > height(node.left.left)) {? ? ? ? node1 = node.left;? ? ? ? node2 = node.left.right;? ? ? ? node.left= node2.right;? ? ? ? node1.right= node2.left;? ? ? ? node2.left= node1;? ? ? ? node2.right= node;? ? ? ? refreshHeight(node);? ? ? ? refreshHeight(node1);returnnode2;? ? }// rrif(height(node.right) > height(node.left) &&? ? ? ? ? ? height(node.right.right) > height(node.right.left)) {? ? ? ? node1 = node.right;? ? ? ? node.right= node1.left;? ? ? ? node1.left= node;? ? ? ? refreshHeight(node);returnnode1;? ? }// rlif(height(node.right) > height(node.left) &&? ? ? ? ? ? height(node.right.left) > height(node.right.right)) {? ? ? ? node1 = node.right;? ? ? ? node2 = node.right.left;? ? ? ? node.right= node2.left;? ? ? ? node1.left= node2.right;? ? ? ? node2.left= node;? ? ? ? node2.right= node1;? ? ? ? refreshHeight(node);? ? ? ? refreshHeight(node1);returnnode2;? ? }returnnode;}

總結(jié)

由插入節(jié)點導(dǎo)致的局部不平衡均會符合上述四種范型之一，只需要按照固定的方式調(diào)整相關(guān)節(jié)點的父子關(guān)系即可使樹恢復(fù)平衡

關(guān)于調(diào)整，很多博客或者書籍中將這種調(diào)整父子關(guān)系的過程稱為?旋轉(zhuǎn)?，這個就見仁見智了，個人覺得這種描述并不容易理解，故本文統(tǒng)一稱為調(diào)整

刪除（remove）

通常情況

對于刪除節(jié)點這個操作來說，有兩個要點：?被刪除節(jié)點的空缺應(yīng)該如何填補?以及?刪除后如何使樹恢復(fù)平衡

被刪除節(jié)點的空缺應(yīng)該如何填補

如果被刪除節(jié)點是葉子節(jié)點，則不需要填補空缺

而如果是枝干節(jié)點，則需要填補空缺，理想的情況是使用某個節(jié)點填補被刪除節(jié)點的空缺后，整棵樹仍然保持平衡?

a) 如果節(jié)點的左右子樹有一棵為空，則使用?非空子樹?填補空缺?

b) 如果節(jié)點的左右子樹均為非空子樹，則使用節(jié)點的左右子樹中?更高?的那棵子樹中的?最大/最小節(jié)點?來填補空缺（如果子樹高度一致則哪邊都可以）

例子：

假設(shè)待刪除節(jié)點為?節(jié)點9?，則應(yīng)當(dāng)使用?左子樹中的最大值?節(jié)點8?來填補空缺

假設(shè)待刪除節(jié)點為?節(jié)點13?，則應(yīng)當(dāng)使用?右子樹中的最小值?節(jié)點14?來填補空缺

假設(shè)待刪除節(jié)點為?節(jié)點2?，則使用?左子樹中的最大值?節(jié)點1.5?或者?右子樹中的最小值?節(jié)點2.5?來填補空缺均可

按照上述方式來填補空缺，可以盡可能保證刪除后整棵樹仍然保持平衡

刪除后如何使樹恢復(fù)平衡

如圖，?葉子節(jié)點12?為被刪除節(jié)點，刪除后不需要填補空缺，但是此時?節(jié)點13?產(chǎn)生了不平衡

不過?節(jié)點13?的不平衡滿足上文所說的不平衡范型中的?RR型?，因此只需要對?節(jié)點13?做對應(yīng)的調(diào)整即可，如圖：

此時?節(jié)點13?所在的子樹經(jīng)過調(diào)整重新達到局部平衡

但是我們緊接著發(fā)現(xiàn)，?節(jié)點11?出現(xiàn)了不平衡，其左子樹高度為4，右子樹高度為2

如果此時按照插入情況下的不平衡范型判斷方法去判斷?節(jié)點11?的不平衡情況屬于哪種范型，會發(fā)現(xiàn)無法滿足四種范型的任一情況

特殊情況

由刪除節(jié)點導(dǎo)致的不平衡，除了會出現(xiàn)插入中所說的四種范型之外，還會出現(xiàn)兩種情況，如圖：

整棵樹初始狀態(tài)為平衡狀態(tài)，此時假設(shè)刪除?節(jié)點13?或?節(jié)點14?，均會導(dǎo)致?節(jié)點11?產(chǎn)生不平衡（左子樹高度3，右子樹高度1）

但是如果仍然按照插入時的方法來判斷不平衡，則會發(fā)現(xiàn)，?節(jié)點4?的左右子樹高度一致，即在滿足了?L?后，后續(xù)無法判斷這種情況屬于哪種范型

對于?R?方向也是一樣

本文稱它們?yōu)?L型?和?R型

不過這兩種情況的處理也很簡單，實際上當(dāng)出現(xiàn)這種情況時，使用?LL型?或?LR型?的調(diào)整方法均可以達到使樹重新平衡的目的

如圖：

兩種調(diào)整方式均可使樹重新平衡，對于?R型?也是一樣，這里不再贅述

代碼實現(xiàn)

publicvoid remove(T key) {if(key ==null) {? ? ? ? thrownewNullPointerException();? ? }? ? root = remove(root, key);}privateNode remove(Node node, T key) {if(node ==null) {? ? ? ? returnnull;? ? }intcmp = key.compareTo(node.key);if(cmp <0) {? ? ? ? node.left= remove(node.left, key);? ? }if(cmp >0){? ? ? ? node.right= remove(node.right, key);? ? }if(cmp ==0) {if(node.left==null|| node.right==null) {? ? ? ? ? ? return node.left==null? node.right: node.left;? ? ? ? }? ? ? ? var successorKey = successorOf(node).key;? ? ? ? node = remove(node, successorKey);? ? ? ? node.key = successorKey;? ? }if(Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {? ? ? ? node = balance(node);? ? }? ? refreshHeight(node);? ? return node;}/** * 尋找被刪除節(jié)點的繼承者 */privateNode successorOf(Node node) {if(node ==null) {? ? ? ? thrownewNullPointerException();? ? }if(node.left==null|| node.right==null) {? ? ? ? return node.left==null? node.right: node.left;? ? }? ? return height(node.left) > height(node.right) ?? ? ? ? ? ? findMax(node.left, node.left.right, node.left.right==null) :? ? ? ? ? ? findMin(node.right, node.right.left, node.right.left==null);}privateNode findMax(Node node, Noderight, boolean rightIsNull) {if(rightIsNull) {? ? ? ? return node;? ? }? ? return findMax((node =right), node.right, node.right==null);}privateNode findMin(Node node, Nodeleft, boolean leftIsNull) {if(leftIsNull) {? ? ? ? return node;? ? }? ? return findMin((node =left), node.left, node.left==null);}

其中用到的?private Node<T> balance(Node<T> node)?方法修改為：

privateNode balance(Node node) {Node node1, node2;// ll & lif(height(node.left) > height(node.right) &&? ? ? ? ? ? height(node.left.left) >= height(node.left.right)) {? ? ? ? node1 = node.left;? ? ? ? node.left= node1.right;? ? ? ? node1.right= node;? ? ? ? refreshHeight(node);returnnode1;? ? }// lrif(height(node.left) > height(node.right) &&? ? ? ? ? ? height(node.left.right) > height(node.left.left)) {? ? ? ? node1 = node.left;? ? ? ? node2 = node.left.right;? ? ? ? node.left= node2.right;? ? ? ? node1.right= node2.left;? ? ? ? node2.left= node1;? ? ? ? node2.right= node;? ? ? ? refreshHeight(node);? ? ? ? refreshHeight(node1);returnnode2;? ? }// rr & rif(height(node.right) > height(node.left) &&? ? ? ? ? ? height(node.right.right) >= height(node.right.left)) {? ? ? ? node1 = node.right;? ? ? ? node.right= node1.left;? ? ? ? node1.left= node;? ? ? ? refreshHeight(node);returnnode1;? ? }// rlif(height(node.right) > height(node.left) &&? ? ? ? ? ? height(node.right.left) > height(node.right.right)) {? ? ? ? node1 = node.right;? ? ? ? node2 = node.right.left;? ? ? ? node.right= node2.left;? ? ? ? node1.left= node2.right;? ? ? ? node2.left= node;? ? ? ? node2.right= node1;? ? ? ? refreshHeight(node);? ? ? ? refreshHeight(node1);returnnode2;? ? }returnnode;}

也就是將?L型?情況包含進了?LL型?，?R型?的情況包含進了?RR型?，因為這兩種范式的調(diào)整要比對應(yīng)的?LR型?/?RL型?的操作數(shù)少

總結(jié)

盡管刪除節(jié)點時會出現(xiàn)特殊的情況，但是仍然可以通過簡單的調(diào)整使樹始終保持平衡

完整代碼

/**

* AVL-Tree

*

* @author Shinobu

* @since 2019/5/7

*/publicclassTree>{privatestaticfinalintMAX_HEIGHT_DIFFERENCE=1;privateNode root;classNode{KTkey;Nodeleft;Noderight;? ? ? ? int height =1;publicNode(KTkey,Nodeleft,Noderight) {? ? ? ? ? ? this.key = key;? ? ? ? ? ? this.left=left;? ? ? ? ? ? this.right=right;? ? ? ? }? ? }publicTree(T... keys) {if(keys == null || keys.length <1) {thrownewNullPointerException();? ? ? ? }? ? ? ? root = newNode<>(keys[0], null, null);for(int i =1; i < keys.length && keys[i] != null; i++) {? ? ? ? ? ? root = insert(root, keys[i]);? ? ? ? }? ? }publicTfind(Tkey) {if(key == null || root == null) {returnnull;? ? ? ? }returnfind(root, key, key.compareTo(root.key));? ? }privateTfind(Node node,Tkey, int cmp) {if(node == null) {returnnull;? ? ? ? }if(cmp ==0) {returnnode.key;? ? ? ? }returnfind(? ? ? ? ? ? ? ? (node = cmp >0? node.right: node.left),? ? ? ? ? ? ? ? key,? ? ? ? ? ? ? ? node == null ?0: key.compareTo(node.key));? ? }publicvoid insert(Tkey) {if(key == null) {thrownewNullPointerException();? ? ? ? }? ? ? ? root = insert(root, key);? ? }privateNode insert(Node node,Tkey) {if(node == null) {returnnewNode<>(key, null, null);? ? ? ? }? ? ? ? int cmp = key.compareTo(node.key);if(cmp ==0) {returnnode;? ? ? ? }if(cmp <0) {? ? ? ? ? ? node.left= insert(node.left, key);? ? ? ? }else{? ? ? ? ? ? node.right= insert(node.right, key);? ? ? ? }if(Math.abs(height(node.left) - height(node.right)) >MAX_HEIGHT_DIFFERENCE) {? ? ? ? ? ? node = balance(node);? ? ? ? }? ? ? ? refreshHeight(node);returnnode;? ? }privateint height(Node node) {if(node == null) {return0;? ? ? ? }returnnode.height;? ? }privatevoid refreshHeight(Node node) {? ? ? ? node.height =Math.max(height(node.left), height(node.right)) +1;? ? }privateNode balance(Node node) {Node node1, node2;// ll & lif(height(node.left) > height(node.right) &&? ? ? ? ? ? ? ? height(node.left.left) >= height(node.left.right)) {? ? ? ? ? ? node1 = node.left;? ? ? ? ? ? node.left= node1.right;? ? ? ? ? ? node1.right= node;? ? ? ? ? ? refreshHeight(node);returnnode1;? ? ? ? }// lrif(height(node.left) > height(node.right) &&? ? ? ? ? ? ? ? height(node.left.right) > height(node.left.left)) {? ? ? ? ? ? node1 = node.left;? ? ? ? ? ? node2 = node.left.right;? ? ? ? ? ? node.left= node2.right;? ? ? ? ? ? node1.right= node2.left;? ? ? ? ? ? node2.left= node1;? ? ? ? ? ? node2.right= node;? ? ? ? ? ? refreshHeight(node);? ? ? ? ? ? refreshHeight(node1);returnnode2;? ? ? ? }// rr & rif(height(node.right) > height(node.left) &&? ? ? ? ? ? ? ? height(node.right.right) >= height(node.right.left)) {? ? ? ? ? ? node1 = node.right;? ? ? ? ? ? node.right= node1.left;? ? ? ? ? ? node1.left= node;? ? ? ? ? ? refreshHeight(node);returnnode1;? ? ? ? }// rlif(height(node.right) > height(node.left) &&? ? ? ? ? ? ? ? height(node.right.left) > height(node.right.right)) {? ? ? ? ? ? node1 = node.right;? ? ? ? ? ? node2 = node.right.left;? ? ? ? ? ? node.right= node2.left;? ? ? ? ? ? node1.left= node2.right;? ? ? ? ? ? node2.left= node;? ? ? ? ? ? node2.right= node1;? ? ? ? ? ? refreshHeight(node);? ? ? ? ? ? refreshHeight(node1);returnnode2;? ? ? ? }returnnode;? ? }publicvoid remove(Tkey) {if(key == null) {thrownewNullPointerException();? ? ? ? }? ? ? ? root = remove(root, key);? ? }privateNode remove(Node node,Tkey) {if(node == null) {returnnull;? ? ? ? }? ? ? ? int cmp = key.compareTo(node.key);if(cmp <0) {? ? ? ? ? ? node.left= remove(node.left, key);? ? ? ? }if(cmp >0){? ? ? ? ? ? node.right= remove(node.right, key);? ? ? ? }if(cmp ==0) {if(node.left== null || node.right== null) {returnnode.left== null ? node.right: node.left;? ? ? ? ? ? }varsuccessorKey = successorOf(node).key;? ? ? ? ? ? node = remove(node, successorKey);? ? ? ? ? ? node.key = successorKey;? ? ? ? }if(Math.abs(height(node.left) - height(node.right)) >MAX_HEIGHT_DIFFERENCE) {? ? ? ? ? ? node = balance(node);? ? ? ? }? ? ? ? refreshHeight(node);returnnode;? ? }privateNode successorOf(Node node) {if(node == null) {thrownewNullPointerException();? ? ? ? }if(node.left== null || node.right== null) {returnnode.left== null ? node.right: node.left;? ? ? ? }returnheight(node.left) > height(node.right) ?? ? ? ? ? ? ? ? findMax(node.left, node.left.right, node.left.right== null) :? ? ? ? ? ? ? ? findMin(node.right, node.right.left, node.right.left== null);? ? }privateNode findMax(Node node,Noderight, boolean rightIsNull) {if(rightIsNull) {returnnode;? ? ? ? }returnfindMax((node =right), node.right, node.right== null);? ? }privateNode findMin(Node node,Nodeleft, boolean leftIsNull) {if(leftIsNull) {returnnode;? ? ? ? }returnfindMin((node =left), node.left, node.left== null);? ? }}

結(jié)語

AVL樹的實現(xiàn)，在了解了不平衡的六種情況，以及對應(yīng)的處理方式后，還是比較簡單且邏輯清晰的

本文實現(xiàn)的AVL樹的增刪查三種操作，全部基于遞歸的算法模式，考慮到在樹足夠大時遞歸的效率問題，本人嘗試進行了一些尾遞歸優(yōu)化，希望這能使操作效率更高一些

后續(xù)

也許

會學(xué)習(xí)并嘗試實現(xiàn)一下紅黑樹，然后對比一下二者的效率

文章如果有謬誤或疏漏，還請務(wù)必指正，感謝萬分