AVL樹的Java實現(xiàn)

leejan97 發(fā)布于2019-08-16 17:13 / 667人閱讀

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

定義

Wikipedia - AVL樹

在計算機(jī)科學(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)系的改變使樹重新平衡

實現(xiàn) 基本結(jié)構(gòu)

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） 四種不平衡范型

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

下面四張圖中的數(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)整后全局重新達(dá)到平衡

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)整后全局重新達(dá)到平衡

RR型

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

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

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

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

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)整后全局重新達(dá)到平衡

代碼實現(xiàn)

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號節(jié)點
 */
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;
}

總結(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)該如何填補(bǔ)以及刪除后如何使樹恢復(fù)平衡

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

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

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

例子：

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

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

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

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

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

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

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

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

但是我們緊接著發(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)?b>L型和R型

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

如圖：

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

代碼實現(xiàn)

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

/**
 * 尋找被刪除節(jié)點的繼承者
 */
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型情況包含進(jìn)了LL型，R型的情況包含進(jìn)了RR型，因為這兩種范式的調(diào)整要比對應(yīng)的LR型/RL型的操作數(shù)少

總結(jié)

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

完整代碼

/**
 * 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);
    }

}

結(jié)語

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

通過對AVL樹的學(xué)習(xí)，可以發(fā)現(xiàn)它是一種“對不平衡非常敏感”的結(jié)構(gòu)——可以容忍的高度差僅為1。這雖然可以讓樹盡可能的平衡，使查找效率盡可能高，但也付出了相應(yīng)的代價：調(diào)整平衡。

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

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

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

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

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

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

GPU云服務(wù)器云服務(wù)器 java菜單樹的實現(xiàn) java二叉樹的構(gòu)建 java樹的使用方法 AVL

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/74461.html

發(fā)表評論

登陸后可評論

0條評論

leejan97

男|高級講師

我要關(guān)注我要私信

TA的文章

【LeetCode 二叉樹專項】尋找重復(fù)的子樹（652）

閱讀 2666·2021-11-15 11:38
#雙11#TmhHost，VPS循環(huán)8折，獨(dú)服永久7折，可選美國CN2+AS9929/中國香港CN2

閱讀 2979·2021-11-02 14:44
MoeCloud：獨(dú)家英國CN2 GIA線路，商寬1000Mbps 帶寬，月付259元起，可解鎖Ne

閱讀 3936·2021-09-26 10:13
Vultr機(jī)房測評 - Vultr新加坡Singapore機(jī)房綜合速度和線路去程回程測試

閱讀 3170·2021-08-13 15:02
CSS Grid響應(yīng)式網(wǎng)頁布局 - W3Schools視頻03

閱讀 855·2019-08-30 15:56
js移動端滑倒頂部加載歷史消息解決方案!

閱讀 1630·2019-08-30 15:53
記一次驚心動魄的前端性能優(yōu)化之旅

閱讀 2407·2019-08-30 13:01
CSS3——過渡（transition）

閱讀 3295·2019-08-29 12:57

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

AVL樹的Java實現(xiàn)

相關(guān)文章

**一文掌握關(guān)于Java數(shù)據(jù)結(jié)構(gòu)所有知識點（歡迎一起完善）**

**Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的基本概念**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — AVL樹**

樹 - （二叉查找樹，紅黑樹，B樹）- 紅黑樹

Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的實現(xiàn)

發(fā)表評論

0條評論

leejan97

男|高級講師

TA的文章

【LeetCode 二叉樹專項】尋找重復(fù)的子樹（652）

#雙11#TmhHost，VPS循環(huán)8折，獨(dú)服永久7折，可選美國CN2+AS9929/中國香港CN2

MoeCloud：獨(dú)家英國CN2 GIA線路，商寬1000Mbps 帶寬，月付259元起，可解鎖Ne

Vultr機(jī)房測評 - Vultr新加坡Singapore機(jī)房綜合速度和線路去程回程測試

CSS Grid響應(yīng)式網(wǎng)頁布局 - W3Schools視頻03

js移動端滑倒頂部加載歷史消息解決方案!

記一次驚心動魄的前端性能優(yōu)化之旅

CSS3——過渡（transition）

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

AVL樹的Java實現(xiàn)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！