Java 資料結構與演算法之樹(AVL)

語言: CN / TW / HK

一、前言

AVL樹歷史

在電腦科學中,AVL 樹以其兩位蘇聯發明家Georgy Adelson-Velsky和 Evgenii Landis的名字命名,他們在 1962 年的論文“資訊組織演算法”中發表了它。它是一種自平衡二叉搜尋樹(BST),這是發明的第一個這樣的資料結構。

二、AVL樹資料結構

AVL 自平衡二叉樹的出現,其目的在於解決二叉搜尋樹退化成連結串列的問題。當我們向BST二叉搜尋樹順序存入1、2、3、4、5、6、7個元素時,它會退化成一條連結串列,因而失去樹查詢的時間複雜度,所以我們需要AVL樹平衡樹高。如圖所示:

那麼AVL樹是怎麼平衡樹高的呢?

當二叉樹的左右分支樹高差不為1時,需要進行左旋或者右旋,來調衡樹高。這有點像開車的時候,如果車頭偏左就往右打方向盤,車頭偏右就往左打方向盤是一個道理。那這個方向盤(左旋、右旋)是怎麼打的呢,主要分以下四種情況;

左旋(新增節點6)

右旋(新增節點1)

左旋+右旋(新增節點4)

右旋+左旋(新增節點3)

條件:節點4,平衡因子為-2,左旋

條件:節點3,平衡因子為2,右旋

條件:節點3,平衡因子為2,右旋。但當節點2平衡因子-1先左旋。

條件:節點2,平衡因子為-2,左旋。但當節點5平衡因子1先右旋。

節點樹高:以節點4為說明,最長的左右分支節點個數,就是節點4的最大樹高。這裡節點4左右孩子節點最長路徑都為2,所以它的樹高為2。同理可計算其他節點樹高。

平衡因子:通過當前節點的左右子節點作差計算平衡因子,之後AVL樹通過平衡因子,定義了什麼時候進行左旋和右旋。

三、AVL樹程式碼實現

對於 AVL 樹的實現與 BST 二叉搜尋樹相比,在樹的節點定義上多了一個樹高的屬性。也有些AVL樹使用的是平衡因子的屬性,就是通過樹高計算後的結果。樹節點程式碼結構如下;

public class  {

    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;
    
    public int height;
    
}

接下來小傅哥就分別通過程式碼講解下一顆AVL樹的左旋、右旋、左旋+右旋、右旋+左旋的程式碼操作。不要擔心這沒有多複雜,只要你能搞清楚左旋,就能搞清楚右旋。兩旋弄懂組合就沒啥難度了。

原始碼地址:https://github.com/fuzhengwei/java-algorithms

本章原始碼:https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stack

動畫演示:https://visualgo.net/zh/bst?slide=1 —— AVL樹初次理解還是比較困難的,可以結合學習內容的同時做一些動畫演示。

1. 左旋

圖解左旋操作;它就是一種摘鏈更換調整節點的處理過程,小傅哥把它分解展示,整個過程如下;

程式碼實現:

protected Node (Node node) {
    Node temp = node.right;
    temp.parent = node.parent;
  
    node.right = temp.left;
    if (node.right != null) {
        node.right.parent = node;
    }
  
    temp.left = node;
    node.parent = temp;
  
    if (temp.parent == null) {
        root = temp;
    } else {
        if (temp.parent.left == node) {
            temp.parent.left = temp;
        } else {
            temp.parent.right = temp;
        }
    }
    return temp;
}

左旋的作用,相當於通過向上遷移樹高差大於1的右子節點來降低樹高的操作。

通過節點4拿到父節點2和右子節點5,把父節點2和右子節點5建立關聯

節點5的左子節點,相當於是大於4小於4的那麼一個值,只不過這裡不體現。那麼這個節點4的左子節點,應該被遷移到節點3的右子節點上。

整理節點5的關係,左子節點為4。左子節點4的父節點為5

如果說遷移上來的節點5無父節點,那麼它就是父節點 root = temp

遷移上來的節點5,找到原節點4是對應父節點的左子節點還是右子節點,對應的設定節點5的左右位置

2. 右旋

圖解右旋操作;它就是一種摘鏈更換調整節點的處理過程,小傅哥把它分解展示,整個過程如下;

程式碼實現:

protected Node (Node node) {
    Node temp = node.left;
    temp.parent = node.parent;
    node.left = temp.right;
    if (node.left != null) {
        node.left.parent = node;
    }
    temp.right = node;
    node.parent = temp;
    if (temp.parent == null) {
        root = temp;
    } else {
        if (temp.parent.left == node) {
            temp.parent.left = temp;
        } else {
            temp.parent.right = temp;
        }
    }
    return temp;
}

右旋的作用,相當於通過向上遷移樹高差大於1的右子節點來降低樹高的操作。

通過節點3拿到父節點4和左子節點2,把父節點7和左子節點2建立關聯

節點2的右子節點,相當於是大於2小於3的那麼一個值,只不過這裡不體現。那麼這個節點2的右子節點,應該被遷移到節點3的左子節點上。

整理節點2的關係,右子節點為3。右子節點3的父節點為2

如果說遷移上來的節點2無父節點,那麼它就是父節點 root = temp

遷移上來的節點2,找到原節點3是對應父節點的左子節點還是右子節點,對應的設定節點2的左右位置

3. 左旋 + 右旋

之所以會有左旋 + 右旋,是因為一次右旋操作沒法平衡樹高,而這種樹的不平衡節點的左子節點的右子節點過長,所以要把不平衡節點的左子節點向左旋轉一次,之後再進行右旋操作。

程式碼實現:

if (factor(node.left) >= 0) {
    Node temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
} else {
    Node temp = super.rotateLeft(node.left);
    refreshHeight(temp.left);
    refreshHeight(temp);
    node.left = temp;
    
    temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
}

4. 右旋 + 左旋

之所以會有右旋 + 左旋,是因為一次左旋操作沒法平衡樹高,而這種樹的不平衡節點的右子節點的左子節點過長,所以要把不平衡節點的右子節點向右旋轉一次,之後再進行左旋操作。

程式碼實現:

if (factor(node.right) <= 0) {
    Node temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
} else {
    Node temp = super.rotateRight(node.right);
    refreshHeight(temp.right);
    refreshHeight(temp);
    node.right = temp;
    
    temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
}

四、AVL樹功能測試

為了驗證AVL樹的實現正確與否,這裡我們做一下隨機節點的插入,如果它能一直保持平衡,那麼它就是一顆可靠 AVL 平衡樹。

單元測試:

public void () {
    AVLTree tree = new AVLTree();
    for (int i = 0; i < 30; i++) {
        tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

測試結果:

輸入節點:61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92

                         /----- 96(0)
                 /----- 95(1)
                 |       \----- 92(0)
         /----- 87(2)
         |       |       /----- 84(0)
         |       \----- 82(1)
 /----- 75(3)
 |       |               /----- 70(0)
 |       |       /----- 69(1)
 |       \----- 69(2)
 |               \----- 65(0)
61(5)
 |               /----- 56(1)
 |               |       \----- 55(0)
 |       /----- 53(2)
 |       |       |       /----- 50(0)
 |       |       \----- 42(1)
 |       |               \----- 38(0)
 \----- 34(4)
         |                       /----- 28(0)
         |               /----- 24(1)
         |               |       \----- 22(0)
         |       /----- 18(2)
         |       |       \----- 11(1)
         |       |               \----- 5(0)
         \----- 3(3)
                 |       /----- 3(1)
                 |       |       \----- 1(0)
                 \----- 1(2)
                         \----- 1(0)


Process finished with exit code 0

隨機插入30個節點,每個節點的順序已經列印,經過AVL左右旋調衡後,二叉結構始終保持樹高平衡因子不超過1,那麼驗證通過。