AVL樹的Java實現

leejan97 發布于2019-08-16 17:13 / 607人閱讀

摘要：容忍不平衡紅黑樹的思路的核心是增大了可容忍的高度差，從而實現既保證查詢效率，也保證了插入和刪除后調整平衡的效率。紅黑樹的查詢效率是略低于樹的，但是紅黑樹通過犧牲了少許查詢效率，使插入刪除后的調整效率達到了常數級別。

定義

Wikipedia - AVL樹

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

理論

實現AVL樹的要點為：每次新增/刪除節點后判斷平衡性然后通過調整使整棵樹重新平衡

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

調整：通過對部分節點的父子關系的改變使樹重新平衡

實現 基本結構

public class Tree> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node root;

    class Node {

        KT key;

        Node left;

        Node right;

        int height = 1;

        public Node(KT key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }
}

插入（insert） 四種不平衡范型

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

下面四張圖中的數字僅代表節點序號，為了后文方便展示調整過程
4、5、6、7號節點代表了四棵高度可以使不平衡成立的子樹（遵循插入的規則）

LL型

LR型

RR型

RL型

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

調整方法

LL型

5號節點作為1號節點的左孩子

1號節點作為2號節點的右孩子

例子（例子中的數字代表節點的值）：

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

LR型

6號節點作為2號節點的右孩子

7號節點作為1號節點的左孩子

2號節點作為3號節點的左孩子

1號節點作為3號節點的右孩子

例子（例子中的數字代表節點的值）：

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

RR型

5號節點作為1號節點的右孩子

1號節點作為2號節點的左孩子

例子（例子中的數字代表節點的值）：

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

RL型

7號節點作為2號節點的左孩子

6號節點作為1號節點的右孩子

2號節點作為3號節點的右孩子

1號節點作為3號節點的左孩子

例子（例子中的數字代表節點的值）：

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

代碼實現

public void insert(T key) {
    if (key == null) {
        throw new NullPointerException();
    }
    root = insert(root, key);
}

private Node insert(Node node, T key) {
    if (node == null) {
        return new Node<>(key, null, null);
    }

    int cmp = key.compareTo(node.key);
    if (cmp == 0) {
        return node;
    }
    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);
    return node;
}

private int height(Node node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

private void refreshHeight(Node node) {
    node.height = Math.max(height(node.left), height(node.right)) + 1;
}

/**
 * 此方法中的node, node1, node2分別代表上文范型中的1、2、3號節點
 */
private Node balance(Node node) {
    Node node1, node2;
    // ll
    if (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);
        return node1;
    }
    // lr
    if (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);
        return node2;
    }
    // rr
    if (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);
        return node1;
    }
    // rl
    if (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);
        return node2;
    }
    return node;
}

總結

由插入節點導致的局部不平衡均會符合上述四種范型之一，只需要按照固定的方式調整相關節點的父子關系即可使樹恢復平衡

關于調整，很多博客或者書籍中將這種調整父子關系的過程稱為旋轉，這個就見仁見智了，個人覺得這種描述并不容易理解，故本文統一稱為調整

刪除（remove） 通常情況

對于刪除節點這個操作來說，有兩個要點：被刪除節點的空缺應該如何填補以及刪除后如何使樹恢復平衡

被刪除節點的空缺應該如何填補

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

而如果是枝干節點，則需要填補空缺，理想的情況是使用某個節點填補被刪除節點的空缺后，整棵樹仍然保持平衡
a) 如果節點的左右子樹有一棵為空，則使用非空子樹填補空缺
b) 如果節點的左右子樹均為非空子樹，則使用節點的左右子樹中更高的那棵子樹中的最大/最小節點來填補空缺（如果子樹高度一致則哪邊都可以）

例子：

假設待刪除節點為節點9，則應當使用左子樹中的最大值節點8來填補空缺

假設待刪除節點為節點13，則應當使用右子樹中的最小值節點14來填補空缺

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

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

刪除后如何使樹恢復平衡

如圖，葉子節點12為被刪除節點，刪除后不需要填補空缺，但是此時節點13產生了不平衡

不過節點13的不平衡滿足上文所說的不平衡范型中的RR型，因此只需要對節點13做對應的調整即可，如圖：

此時節點13所在的子樹經過調整重新達到局部平衡

但是我們緊接著發現，節點11出現了不平衡，其左子樹高度為4，右子樹高度為2

如果此時按照插入情況下的不平衡范型判斷方法去判斷節點11的不平衡情況屬于哪種范型，會發現無法滿足四種范型的任一情況

特殊情況

由刪除節點導致的不平衡，除了會出現插入中所說的四種范型之外，還會出現兩種情況，如圖：

整棵樹初始狀態為平衡狀態，此時假設刪除節點13或節點14，均會導致節點11產生不平衡（左子樹高度3，右子樹高度1）

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

對于R方向也是一樣

本文稱它們為L型和R型

不過這兩種情況的處理也很簡單，實際上當出現這種情況時，使用LL型或LR型的調整方法均可以達到使樹重新平衡的目的

如圖：

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

代碼實現

public void remove(T key) {
    if (key == null) {
        throw new NullPointerException();
    }
    root = remove(root, key);
}

private Node remove(Node node, T key) {
    if (node == null) {
        return null;
    }

    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) {
            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;
}

/**
 * 尋找被刪除節點的繼承者
 */
private Node successorOf(Node node) {
    if (node == null) {
        throw new NullPointerException();
    }
    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);
}

private Node findMax(Node node, Node right, boolean rightIsNull) {
    if (rightIsNull) {
        return node;
    }
    return findMax((node = right), node.right, node.right == null);
}

private Node findMin(Node node, Node left, boolean leftIsNull) {
    if (leftIsNull) {
        return node;
    }
    return findMin((node = left), node.left, node.left == null);
}

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

private Node balance(Node node) {
    Node node1, node2;
    // ll & l
    if (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);
        return node1;
    }
    // lr
    if (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);
        return node2;
    }
    // rr & r
    if (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);
        return node1;
    }
    // rl
    if (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);
        return node2;
    }
    return node;
}

也就是將L型情況包含進了LL型，R型的情況包含進了RR型，因為這兩種范式的調整要比對應的LR型/RL型的操作數少

總結

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

完整代碼

/**
 * AVL-Tree
 *
 * @author Shinobu
 * @since 2019/5/7
 */
public class Tree> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node root;

    class Node {

        KT key;

        Node left;

        Node right;

        int height = 1;

        public Node(KT key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }

    public Tree(T... keys) {
        if (keys == null || keys.length < 1) {
            throw new NullPointerException();
        }

        root = new Node<>(keys[0], null, null);
        for (int i = 1; i < keys.length && keys[i] != null; i++) {
            root = insert(root, keys[i]);
        }
    }

    public T find(T key) {
        if (key == null || root == null) {
            return null;
        }
        return find(root, key, key.compareTo(root.key));
    }

    private T find(Node node, T key, int cmp) {
        if (node == null) {
            return null;
        }

        if (cmp == 0) {
            return node.key;
        }

        return find(
                (node = cmp > 0 ? node.right : node.left),
                key,
                node == null ? 0 : key.compareTo(node.key));
    }

    public void insert(T key) {
        if (key == null) {
            throw new NullPointerException();
        }
        root = insert(root, key);
    }

    private Node insert(Node node, T key) {
        if (node == null) {
            return new Node<>(key, null, null);
        }

        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node;
        }
        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);
        return node;
    }

    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private void refreshHeight(Node node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    private Node balance(Node node) {
        Node node1, node2;
        // ll & l
        if (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);
            return node1;
        }
        // lr
        if (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);
            return node2;
        }
        // rr & r
        if (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);
            return node1;
        }
        // rl
        if (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);
            return node2;
        }
        return node;
    }

    public void remove(T key) {
        if (key == null) {
            throw new NullPointerException();
        }
        root = remove(root, key);
    }

    private Node remove(Node node, T key) {
        if (node == null) {
            return null;
        }

        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) {
                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;
    }
    
    private Node successorOf(Node node) {
        if (node == null) {
            throw new NullPointerException();
        }
        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);
    }

    private Node findMax(Node node, Node right, boolean rightIsNull) {
        if (rightIsNull) {
            return node;
        }
        return findMax((node = right), node.right, node.right == null);
    }

    private Node findMin(Node node, Node left, boolean leftIsNull) {
        if (leftIsNull) {
            return node;
        }
        return findMin((node = left), node.left, node.left == null);
    }

}

結語

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

通過對AVL樹的學習，可以發現它是一種“對不平衡非常敏感”的結構——可以容忍的高度差僅為1。這雖然可以讓樹盡可能的平衡，使查找效率盡可能高，但也付出了相應的代價：調整平衡。

它的插入元素引發的調整的最壞時間復雜度為O(1)，但是刪除引發的最壞時間復雜度為O(logN)，這正是AVL樹的弊端所在。

所以后來的2-3樹、2-3-4樹、紅黑樹都嘗試對這種弊端進行了改進，改進的思路可以大概理解為兩種：

使樹完全平衡
這是2-3樹和2-3-4樹這兩種結構嘗試的方向。因為造成AVL樹刪除時“雪崩”的原因正是因為它所能容忍的這一點高度差，在高度差大量積累后，刪除“薄弱”側的節點，就會導致需要大量的調整才能恢復平衡。而如果完全消除高度差，就可以避免這種情況了。
然而實際的情況是這兩種樹的實現都算不上簡單，而且反而使插入的調整行為的時間復雜度變為了O(logN)。

容忍不平衡
紅黑樹的思路的核心是增大了可容忍的高度差，從而實現既保證查詢效率（O(logN)），也保證了插入和刪除后調整平衡的效率（O(1)）。
紅黑樹的查詢效率（2 * O(logN)）是略低于AVL樹（O(logN)）的，但是紅黑樹通過犧牲了少許查詢效率，使插入刪除后的調整效率達到了常數級別。
紅黑樹算法中的著色策略、對于父節點、叔節點、祖父節點等等節點的顏色判斷、以及相應的調整策略都是經過極度抽象后的結果，因此想要從頭到尾徹底理解紅黑樹的設計思想其實還是有些難度的（理解設計思想并非照著抽象好的五條規則照本宣科）

以上，希望本文對讀到的朋友能有所幫助

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

GPU云服務器云服務器 java菜單樹的實現 java二叉樹的構建 java樹的使用方法 AVL

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74461.html

一文掌握關于Java數據結構所有知識點（歡迎一起完善）

摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。在我們學習Java的時候，很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...

keithxiaoy 2019-08-15 15:54 評論0 收藏0
Python數據結構——AVL樹的基本概念

摘要：我們知道，當樹變得不平衡時和操作會使二叉搜索樹的性能降低到。樹實現抽象數據類型就像一個普通的二叉搜索樹，唯一不同的是這棵樹的工作方式。我們通過比較每個節點的左右子樹的高度完成比較。平衡二叉搜索樹在上一節中我們討論了建立一個二叉搜索樹。我們知道，當樹變得不平衡時get和put操作會使二叉搜索樹的性能降低到O(n)。在這一節中我們將看到一種特殊的二叉搜索樹，它可以自動進行調整，以確保樹...

jiekechoo 2019-07-24 18:26 評論0 收藏0
學習JavaScript數據結構與算法 — AVL樹

摘要：可以看到，一次左單旋將右側子樹的高度減小了，而左側子樹的高度增加了。如圖，對進行右單旋，需要左子樹的右子樹的高度小于等于左子樹的高度，否則不能達到平衡的效果，只是把不平衡性從左邊轉移到了右邊。 AVL樹普通二叉搜索樹可能出現一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會導致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念，AVL樹（阿德爾森-維爾斯和蘭迪斯樹...

impig33 2019-08-21 11:31 評論0 收藏0
樹 - （二叉查找樹，紅黑樹，B樹）- 紅黑樹

摘要：需要執行的操作依次是首先，將紅黑樹當作一顆二叉查找樹，將該節點從二叉查找樹中刪除然后，通過旋轉和重新著色等一系列來修正該樹，使之重新成為一棵紅黑樹。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨關于二叉樹的基本知識，可以參見：Java 實現基本數據結構 2(樹) 以下是算法導論第13章的學...

yangrd 2019-08-14 12:05 評論0 收藏0
Python數據結構——AVL樹的實現

摘要：一旦子樹平衡因子為零，那么父節點的平衡因子不會發生改變。新根的父節點將成為舊根的父節點。因為其他操作都是移動整個子樹，被移動的子樹內的節點的平衡因子不受旋轉的影響。讓表示以為根節點的子樹的高度。既然，我們已經證明，保持 AVL 樹的平衡將會使性能得到很大的提升，那我們看看如何在程序中向樹插入一個新的鍵值。因為所有的新鍵是作為葉節點插入樹的，而新葉子的平衡因子為零，所以我們對新插入的節...

Pink 2019-07-31 12:22 評論0 收藏0