自己動手實現java資料結構（七） AVL樹

摘要： 1.AVL樹介紹 前面我們已經介紹了二叉搜尋樹。普通的二叉搜尋樹在插入、刪除資料時可能使得全樹的資料分佈不平衡，退化，導致二叉搜尋樹最關鍵的查詢效率急劇降低。這也引出了平衡二叉搜尋樹的概念，平衡二叉搜尋樹在此前的基礎上，通過一系列的等價變換使二叉搜尋樹得以始終處於" 平衡 ...

1.AVL樹介紹

前面我們已經介紹了二叉搜尋樹。普通的二叉搜尋樹在插入、刪除資料時可能使得全樹的資料分佈不平衡，退化，導致二叉搜尋樹最關鍵的查詢效率急劇降低。這也引出了平衡二叉搜尋樹的概念，平衡二叉搜尋樹在此前的基礎上，通過一系列的等價變換使二叉搜尋樹得以始終處於" 平衡 "的狀態，擁有穩定且高效的查詢效率。

AVL樹是最早被電腦科學家發明的自平衡二叉搜尋樹，AVL樹得名於它的發明者G. M.  A delson- V elsky和E. M.  L andis，他們在1962年的論文《An algorithm for the organization of information》中發表了它。

不同的平衡二叉搜尋樹對所謂"平衡"有不同的定義，AVL樹認為 當所有節點的左右子樹高度之差不超過正負1時，全樹是平衡的 。

在插入新節點和刪除舊節點之後，AVL樹會判斷當前是否有節點失去平衡，並對失衡的節點進行相應的重平衡操作，恢復到AVL樹定義的適度平衡狀態。

2.AVL樹重平衡原理

2.1 等價變換介紹

二叉搜尋樹有一個重要的特性： 所儲存元素的中序遍歷次序是有序的 ，這也是二叉搜尋樹能夠使用二分法加速查詢的基礎。

對於同一中序遍歷次序，二叉搜尋樹的拓撲結構可以是多樣的，在保持二叉搜尋樹中序遍歷次序不變的情況下 (等價) ，對其拓撲結構進行一系列變換 (變換) ，被稱為 等價變換 。

等價變換是平衡二叉搜尋樹重平衡操作的理論基礎。

2.2 等價變換方式

等價變換的基本操作有兩種：

順時針旋轉(zig)，可以形象的理解為x->y箭頭方向下午兩點變成了下午四點，也被稱為右旋

逆時針旋轉(zag)，可以形象的理解為y->x箭頭方向上午十點變成了上午八點，也被稱為左旋

順時針旋轉和逆時針旋轉的操作是互逆的，複雜等價變換操作可以看成是由這兩種基本操作組合而成。

順時針旋轉：

逆時針旋轉：

2.3 AVL樹的失衡狀態及重平衡

在瞭解如何恢復AVL樹平衡狀態之前，需要先理解幾個關鍵點：

1.無論是插入新節點還是刪除老節點，最多隻會導致插入/刪除節點位置的上層的歷代祖先節點失去平衡(數量大致為 logN)，而不會導致全樹節點都失去平衡，因此只需要判斷其歷代祖先節點的平衡狀態，即可判斷其是否破壞了AVL樹的平衡狀態

2.當原先 較高的子樹 中 插入新節點 時，可能會導致歷代祖先節點失衡(部分祖先節點，而非全部)

3.當原先 較低的子樹 中 刪除老節點 時，可能會導致歷代祖先節點失衡(部分祖先節點，而非全部)

針對AVL樹的失衡節點進行重平衡時，主要關注 失衡節點自身(N Node)、引起失衡方向的孩子節點(S Son)、 引起失衡方向的 孫子節點(GS GrandSon) 及所屬子樹，對其進行等價變換操作，使之恢復平衡。

我們從失衡節點出發，依據失衡節點和其引起失衡方向的孩子節點、其引起失衡方向的孫子節點的共同構成的拓撲結構，共以下四種形態：

2.3.1 左左形

左左形 插入節點引起失衡及重平衡：

左左形 刪除節點引起失衡及重平衡：

2.3.3 左右形

左右形 插入節點引起失衡及重平衡：

左右形 刪除節點引起失衡及重平衡：

2.3.2 右右形

右右形和左左形是映象的拓撲結構，失衡場景和重平衡手段與 "2.3.1 左左形" 原理相同，限於篇幅，不再展開說明。

2.3.4 右左形

右左形和左右形是映象的拓撲結構，失衡場景和重平衡手段與 "2.3.2 左右形" 原理相同，限於篇幅，不再展開說明。

2.3.5 插入和刪除操作重平衡的區別

在示意圖中，注意觀察標識樹高層次的 橫向細長的白色箭頭 。

插入和刪除操作會導致操作節點位置的歷代祖先失去平衡，這需要從低到高依次檢查平衡狀態並進行重平衡處理。

插入新節點導致失衡並重平衡的過程中，當前失衡節點( 最低的失衡祖先節點 )所在 子樹的高度 在重平衡操作完成後和未插入新節點之前 是一樣的 。因而當最低位置的祖先節點恢復了平衡後，更高的祖先節點也將自動的恢復平衡（因為插入前是平衡的，而插入後失衡子樹的高度在重平衡後也和原先一致了）。

刪除老節點導致失衡並重平衡的過程中，當前失衡節點( 最低的 失衡 祖先節點 )所在 子樹的高度 在重平衡操作完成後和未插入新節點之前 可能是不一樣的(所在子樹高度降低1) 。因而當最低位置的祖先節點恢復平衡後，可能會導致更高的祖先節點進而失去平衡，這種現象會向上逐層傳播。最壞的極端情況下，每當恢復一個較低的祖先節點平衡時，都會導致更高一層祖先節點失衡，直至根節點完成重平衡，這樣的重平衡操作最多需要執行 (logN) 次。

2.4 3+4重構

前面介紹了針對不同失衡狀態拓撲結構進行重平衡的方法，都是使用一 次或多次旋轉 的方式完成的。

如果我們聚焦於 重平衡操作所涉及的元素 ，會發現其實質只是改變了 Node ， Son ， GrandSon 三個節點及所掛載的四顆子樹 (T0,T1,T2,T3) 的位置關係。更為重要的是，無論是左左形還是其它三種形狀，其重平衡完成之後的拓撲結構是一樣的， 區別只在於N，S，GS三個節點的相對位置不同 。

因此，便有了另一種更高效的重平衡等價變換的方式，被稱為 "3+4重構" 。3+4重構在重平衡時，暴力的將元素打散， 並不使用旋轉的技巧 ，而是直接改變節點和節點、節點和子樹之間的引用關係，一口氣將其轉變為重平衡之後的最終拓撲結構，直達目標。

3.AVL樹實現細節

3.1 二叉搜尋樹拓展

AVL樹的實現繼承自前面介紹的普通二叉搜尋樹—TreeMap類。由於AVL樹通過樹高作為判斷平衡的依據，因此在二叉搜尋樹 TreeMap 的節點中增加了一個 height(高度) 屬性。

/**
* 二叉搜尋樹 內部節點
* */
static class EntryNode<K,V> implements Map.EntryNode<K,V>{
/**
* key值
* */
K key;

/**
* value值
* */
V value;

/**
* 高度值
* */
int height;

/**
* 左孩子節點
* */
EntryNode<K,V> left;

/**
* 右孩子節點
* */
EntryNode<K,V> right;

/**
* 雙親節點
* */
EntryNode<K,V> parent;

EntryNode(K key, V value) {
this.key = key;
this.value = value;
this.height = 1;
}

EntryNode(K key, V value,EntryNode<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
this.height = 1;
}

@Override
public K getKey() {
return key;
}

@Override
public V getValue() {
return value;
}

@Override
public void setValue(V value) {
this.value = value;
}

@Override
public String toString() {
return key + "=" + value + " height=" + height;
}
}

3.2 輔助方法

在AVL樹的實現過程中，存在一些通用的，細節的邏輯，將其抽取成輔助函式，簡化主要程式碼邏輯，增強程式碼可讀性和可維護性。

/**
* 當前節點 是否滿足AVL樹約定的平衡條件
* */
private boolean isAVLBalanced(EntryNode<K,V> entryNode){
//獲得 左子樹高度
int leftChildHeight = getHeight(entryNode.left);
//獲得右子樹高度
int rightChildHeight = getHeight(entryNode.right);

//獲得左右子樹高度差
int difference = leftChildHeight - rightChildHeight;

//高度差絕對值在1之內,認為是滿足AVL平衡條件
return -1 <= difference && difference <= 1;
}

/**
* 更新當前節點高度
* */
private void updateHeight(EntryNode<K,V> entryNode){
int leftHeight = getHeight(entryNode.left);
int rightHeight = getHeight(entryNode.right);

//左右子樹高度較高者 + 1
entryNode.height = 1 + Math.max(leftHeight,rightHeight);
}

/**
* 獲得當前節點的高度
* */
private int getHeight(EntryNode<K,V> entryNode){
if(entryNode == null){
return 0;
}else{
return entryNode.height;
}
}

/**
* 獲得較高子樹分支孩子節點
*/
private EntryNode<K,V> getTallerChild(EntryNode<K,V> entryNode){
int leftChildHeight = getHeight(entryNode.left);
int rightChildHeight = getHeight(entryNode.right);

if(leftChildHeight > rightChildHeight){
//左子樹高度 > 右子樹高度
return entryNode.left;
}else{
//左子樹高度 <= 右子樹高度
return entryNode.right;
}
}

/**
* 是否是左孩子
* */
private boolean isLeftChild(EntryNode<K,V> parent,EntryNode<K,V> target){
return getRelativeByParent(parent,target) == RelativePosition.LEFT;
}

3.3 3+4重構實現

refactor34方法：方法的引數為3+4重構目標拓撲結構所需的三個節點(左，中，右)，左右孩子的分別掛載的四顆子樹。在 refactor34 方法中，依照3+4重構的原理直接調整節點和子樹的關係引用，拼接成最終的所需的結果。

rotateAt方法：方法的引數為重平衡所涉及到的祖孫三代節點( Node、Son、GrandSon )，通過判斷 N、S、GS 的拓撲結構，決定呼叫 refactor34 方法時傳遞的引數。方法的返回值為3+4重構後的子樹樹根節點，便於重平衡操作之後，將重構後新的子樹重新接入整顆AVL樹中。

/**
* 3+4 重構
* */
private void refactor34(
EntryNode<K,V> leftNode, EntryNode<K,V> middleNode, EntryNode<K,V> rightNode,
EntryNode<K,V> llChild, EntryNode<K,V> lrChild,
EntryNode<K,V> rlChild, EntryNode<K,V> rrChild){

//調整 左節點和對應子樹的拓撲結構
leftNode.left = llChild;
if(llChild != null){
llChild.parent = leftNode;
}

leftNode.right = lrChild;
if(lrChild != null){
lrChild.parent = leftNode;
}
//更新高度
updateHeight(leftNode);

//調整 右節點和對應子樹的拓撲結構
rightNode.left = rlChild;
if(rlChild != null){
rlChild.parent = rightNode;
}

rightNode.right = rrChild;
if(rrChild != null){
rrChild.parent = rightNode;
}
//更新高度
updateHeight(rightNode);

//調整 中間節點 和左、右節點的拓撲結構
middleNode.left = leftNode;
middleNode.right = rightNode;

leftNode.parent = middleNode;
rightNode.parent = middleNode;
//更新高度
updateHeight(middleNode);
}

/**
* 進行旋轉,使用3+4重構完成重平衡
* @return 重構之後子樹的樹根節點
* */
private EntryNode<K,V> rotateAt(EntryNode<K,V> currentNode,EntryNode<K,V> sonNode,EntryNode<K,V> grandSonNode){
if(isLeftChild(currentNode,sonNode)){
//左 zig
if(isLeftChild(sonNode,grandSonNode)){
//左-左zig-zig旋轉
refactor34(grandSonNode,sonNode,currentNode,
grandSonNode.left,grandSonNode.right,sonNode.right,currentNode.right);

return sonNode;
}else{
//左-右zig-zag旋轉
refactor34(sonNode,grandSonNode,currentNode,
sonNode.left,grandSonNode.left,grandSonNode.right,currentNode.right);

return grandSonNode;
}
}else{
//右 zag
if(isLeftChild(sonNode,grandSonNode)){
//右-左zag-zig旋轉
refactor34(currentNode,grandSonNode,sonNode,
currentNode.left,grandSonNode.left,grandSonNode.right,sonNode.right);

return grandSonNode;
}else{
//右-右zag-zag旋轉
refactor34(currentNode,sonNode,grandSonNode,
currentNode.left,sonNode.left,grandSonNode.left,grandSonNode.right);

return sonNode;
}
}
}

3.4 插入方法重寫

AVL樹的實現中，重寫了普通二叉搜尋樹的插入方法( put )，整體邏輯和之前TreeMap的實現大致一樣，唯一的區別在於，當插入了新的節點之後，會呼叫 afterNewNodeInsert 方法，進行AVL樹重平衡的一系列操作。

afterNewNodeInsert方法：

引數為新插入的節點。從下至上，遍歷檢查新插入節點的歷代祖先，判斷其是否失衡。一旦發現當前迭代的祖先節點失衡，則呼叫 rotateAt 方法，使其恢復平衡，全樹重新接入子樹；

插入節點時，導致的失衡不會向上傳播，所屬子樹的高度能夠復原，在恢復平衡之後，直接結束方法的執行，不再繼續向上檢查。另外，對於未失衡的祖先節點，其 子樹插入新節點 時 可能 會導致 高度上升 ，因此需要更新其高度。

@Override
public V put(K key, V value) {
if(this.root == null){
this.root = new EntryNode<>(key,value);
this.size++;
return null;
}

//獲得目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition == RelativePosition.CURRENT){
//目標節點存在於當前容器

//暫存之前的value
V oldValue = targetEntryNode.target.value;
//替換為新的value
targetEntryNode.target.value = value;
//返回之前的value
return oldValue;
}else{
//目標節點不存在於當前容器
EntryNode<K,V> parent = targetEntryNode.parent;
EntryNode<K,V> newEntryNode = new EntryNode<>(key,value,parent);
if(targetEntryNode.relativePosition == RelativePosition.LEFT){
//目標節點位於左邊
parent.left = newEntryNode;
}else{
//目標節點位於右邊
parent.right = newEntryNode;
}

//插入新節點後進行重平衡操作
afterNewNodeInsert(newEntryNode);

this.size++;
return null;
}
}

/**
* 插入後 重平衡操作
* @param newEntryNode 新插入的節點
* */
private void afterNewNodeInsert(EntryNode<K,V> newEntryNode){
EntryNode<K,V> currentAncestorNode = newEntryNode.parent;

//遍歷新插入節點的祖先節點,逐層向上
while(currentAncestorNode != null){
//判斷當前祖先節點是否失去平衡
if(!isAVLBalanced(currentAncestorNode)){
//不平衡

//獲得重構之前 失衡節點的父節點及其相對位置，用於之後重新連線重平衡後的子樹
EntryNode<K,V> parent = currentAncestorNode.parent;

//獲得更高子樹分支對應的孫輩節點，決定AVL樹重平衡的策略
EntryNode<K,V> tallerSonNode = getTallerChild(currentAncestorNode);
EntryNode<K,V> tallerGrandSonNode = getTallerChild(tallerSonNode);
//以孫輩節點為基準，進行旋轉，重平衡
EntryNode<K,V> newSubTreeRoot = rotateAt(currentAncestorNode,tallerSonNode,tallerGrandSonNode);

//重構之後的子樹 重新和全樹對接
newSubTreeRoot.parent = parent;
//可能currentAncestorNode是根節點，不存在雙親節點
if(parent != null){
//原子樹根節點的雙親節點 和新的子樹進行連線
if(isLeftChild(parent,currentAncestorNode)){
parent.left = newSubTreeRoot;
}else{
parent.right = newSubTreeRoot;
}
}else{
this.root = newSubTreeRoot;
}
//插入時，最低失衡節點重平衡後，全樹即恢復平衡，因此結束迴圈
return;
}else{
//平衡

//更新當前祖先節點的高度
updateHeight(currentAncestorNode);
}

//指向上一層祖先節點
currentAncestorNode = currentAncestorNode.parent;
}
}

3.5 刪除方法重寫

AVL樹的實現中，重寫了普通二叉搜尋樹的刪除方法( remove )，整體邏輯和之前TreeMap的實現大致一樣，唯一的區別在於，當刪除了之前老的節點之後，會呼叫 afterNodeRemove 方法，進行AVL樹重平衡的一系列操作。

afterNodeRemove方法：

引數為之前被刪除節點的雙親節點。從下至上，遍歷檢查被刪除節點雙親的歷代祖先，判斷其是否失衡。一旦發現當前迭代的祖先節點失衡，則呼叫 rotateAt 方法，使其恢復平衡，全樹重新接入子樹。

刪除節點時，失衡現象會向上傳播，因此必須一直向上遍歷至根節點。另外，對於未失衡的祖先節點， 子樹刪除老節點 時 可能 會導致 高度降低 ，因此需要更新其高度。

 @Override
public V remove(K key) {
if(this.root == null){
return null;
}

//查詢目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition != RelativePosition.CURRENT){
//沒有找到目標節點
return null;
}else{
//找到了目標節點
EntryNode<K,V> target = targetEntryNode.target;
//先儲存被刪除節點 刪除之前的雙親節點
EntryNode<K,V> parent = target.parent;

//從二叉樹中刪除目標節點
deleteEntryNode(target);

//刪除節點後，對其歷代祖先節點進行重平衡操作
afterNodeRemove(parent);

return targetEntryNode.target.value;
}
}

/**
* 插入後 重平衡操作
* @param deletedNode 被刪除的節點
* */
private void afterNodeRemove(EntryNode<K,V> deletedNode){
EntryNode<K,V> currentAncestorNode = deletedNode;

//遍歷新插入節點的祖先節點,逐層向上
while(currentAncestorNode != null){
//判斷當前祖先節點是否失去平衡
if(!isAVLBalanced(currentAncestorNode)){
//不平衡

//獲得重構之前 失衡節點的父節點及其相對位置
EntryNode<K,V> parent = currentAncestorNode.parent;
//獲得更高子樹分支對應的孫輩節點，決定AVL樹重平衡的策略
EntryNode<K,V> tallerSonNode = getTallerChild(currentAncestorNode);
EntryNode<K,V> tallerGrandSonNode = getTallerChild(tallerSonNode);
//以孫輩節點為基準，進行旋轉，重平衡
EntryNode<K,V> newSubTreeRoot = rotateAt(currentAncestorNode,tallerSonNode,tallerGrandSonNode);

//重構之後的子樹 重新和全樹對接
newSubTreeRoot.parent = parent;
//可能currentAncestorNode是根節點，不存在雙親節點
if(parent != null){
//原子樹根節點的雙親節點 和新的子樹進行連線
if(isLeftChild(parent,currentAncestorNode)){
parent.left = newSubTreeRoot;
}else{
parent.right = newSubTreeRoot;
}
}else{
this.root = newSubTreeRoot;
}
}else{
//平衡

//更新當前祖先節點的高度
updateHeight(currentAncestorNode);
}

//指向上一層祖先節點
currentAncestorNode = currentAncestorNode.parent;
}
}

4.AVL樹效能

4.1 插入效能

AVL樹的插入操作引起的失衡不會向上傳播，只需要一次重平衡操作。

相比普通二叉搜尋樹，AVL樹插入重平衡操作額外引入的 時間複雜度為O(1) ，十分高效。

4.2 刪除效能

AVL樹的刪除操作引起的失衡會向上傳播，最壞情況下每一個祖先節點都需要進行重平衡。

相比普通二叉搜尋樹，AVL樹刪除重平衡操作額外引入的時間複雜度為 O(logN) ，刪除效率比起紅黑樹 (O(1)) 等更加高效的BBST相對要差。

4.3 查詢效能

AVL樹適度平衡的條件比較苛刻，因此AVL樹是非常接近完全二叉樹的一種BBST。其查詢效率和紅黑樹等綜合性能更加優秀的BBST相比，查詢時，雖然漸進的時間複雜度都為 O(logN) ，但在常數倍率上看，效率要稍高一點點。

5.AVL樹總結

AVL樹作為最早被髮明的自平衡二叉搜尋樹，其刪除效率與隨後被髮明的紅黑樹、伸展樹相比，相差一個數量級 (O(logN) vs O(1)) 。其主要原因是紅黑樹等BBST在"平衡"的定義上進一步放鬆了標準，全樹結構不如AVL樹那麼緊湊，略為降低了查詢效率，但換來了刪除效率的巨大提升。

AVL樹作為一種相對效率較低的BBST，其原理相比紅黑樹來說更為簡單。我個人認為，理解AVL樹是理解更為強大、複雜的BBST的基礎之一。希望大家能更好的理解平衡二叉搜尋樹，更好的理解自己所使用的資料結構，從而寫出更高效，易維護的程式。

本系列部落格的程式碼在我的 github上： https://github.com/1399852153/DataStructures   ，存在許多不足之處，請多多指教。