Java數(shù)據(jù)結構之平衡二叉樹的實現(xiàn)詳解

更新時間：2022年03月30日 09:06:09 作者：gonghr

平衡二叉樹又被稱為AVL樹（有別于AVL算法），且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。本文將詳解介紹一下平衡二叉樹的原理與實現(xiàn)，需要的可以參考一下

定義

動機：二叉查找樹的操作實踐復雜度由樹高度決定，所以希望控制樹高，左右子樹盡可能平衡。

平衡二叉樹（AVL樹）：稱一棵二叉查找樹為高度平衡樹，當且僅當或由單一外結點組成，或由兩個子樹形 Ta 和 Tb 組成，并且滿足：

|h(Ta) - h(Tb)| <= 1，其中 h(T) 表示樹 T 的高度
Ta 和 Tb 都是高度平衡樹

即：每個結點的左子樹和右子樹的高度最多差 1 的二叉查找樹。

設 T 為高度平衡樹中結點 q 的平衡系數(shù)為 q 的右子樹高度減去左子樹高度
高度平衡樹所以結點的平衡系數(shù)只可能為：-1, 0, 1

結點結構

key：關鍵字的值

value：關鍵字的存儲信息

height：樹的高度（只有一個結點的樹的高度為 1）

left：左子樹根結點的的引用

right：右子樹根結點的引用

class AVLNode<K extends Comparable<K>, V> {
    public K key;
    public V value;
    public int height;
    public AVLNode<K, V> left;
    public AVLNode<K, V> right;

    public AVLNode(K key, V value, int height) {
        this.key = key;
        this.value = value;
        this.height = height;
    }
}

查找算法

同二叉查找樹的查找算法：Java數(shù)據(jù)結構之二叉查找樹的實現(xiàn)

插入算法

AVL 樹是一種二叉查找樹，故可以使用二叉查找樹的插入方法插入結點，但插入一個新結點時，有可能破壞 AVL 樹的平衡性。

如果發(fā)生這種情況，就需要在插入結點后對平衡樹進行調整，恢復平衡的性質。實現(xiàn)這種調整的操作稱為“旋轉”。

在插入一個新結點 X 后，應調整失去平衡的最小子樹，即從插入點到根的路徑向上找第一個不平衡結點 A。

平衡因子：該結點的左子樹高度和右子樹高度的差值。如果差值的絕對值小于等于 1，則說明該結點平衡，如果差值的絕對值為 2（不會出現(xiàn)其他情況），則說明該結點不平衡，需要做平衡處理。

造成結點 A 不平衡的的原因以及調整方式有以下幾種情況。

LL 型

A 結點的平衡因子為 2，說明該結點是最小不平衡結點，需要對 A 結點進行調整。問題發(fā)生在 A 結點左子結點的左子結點，所以為 LL 型。

扁擔原理：右旋

將 A 的左孩子 B 提升為新的根結點；
將原來的根結點 A 降為 B 的右孩子；
各子樹按大小關系連接(BL 和 AR 不變，BR 調整為 A 的左子樹)。
高度調整：由于調整后 B 的高度依賴于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

    private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.left;
        a.left = b.right;
        b.right = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
        return b;
    }

RR 型

A 結點的平衡因子為 2，說明該結點是最小不平衡結點，需要對 A 結點進行調整。問題發(fā)生在 A 結點右子結點的右子結點，所以為 RR 型。

扁擔原理：左旋

將 A 的右孩子 B 提升為新的根結點；
將原來的根結點 A 降為 B 的左孩子；
各子樹按大小關系連接(AL 和 BR 不變，BL 調整為 A 的右子樹)。
高度調整：由于調整后 B 的高度依賴于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

    private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.right;
        a.right = b.left;
        b.left = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
        return b;
    }

LR 型

A 結點的平衡因子為 2，說明該結點是最小不平衡結點，需要對 A 結點進行調整。問題發(fā)生在 A 結點左子結點的右子結點，所以為 LR 型。

從旋轉的角度：對 B 左旋，然后對 A 右旋
將 B 的左孩子 C 提升為新的根結點；
將原來的根結點 A 降為 C 的右孩子；
各子樹按大小關系連接(BL 和 AR 不變，CL 和 CR 分別調整為 B 的右子樹和 A 的左子樹)。

    private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
        a.left = leftRotate(a.left);   // 對 B 左旋
        return rightRotate(a);         // 對 A 右旋
    }

RL 型

A 結點的平衡因子為 2，說明該結點是最小不平衡結點，需要對 A 結點進行調整。問題發(fā)生在 A 結點右子結點的左子結點，所以為 RL 型。

從旋轉的角度：對 B 右旋，然后對 A 左旋
將 B 的左孩子 C 提升為新的根結點；
將原來的根結點 A 降為 C 的左孩子；
各子樹按大小關系連接(AL 和 BR 不變，CL 和 CR 分別調整為 A 的右子樹和 B 的左子樹)。

    private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
        a.right = rightRotate(a.right);
        return leftRotate(a);
    }

插入方法

根結點默認高度為 1

某結點的左右子樹高度差的絕對值為 2，則需要進行平衡處理

I.左子樹高

key 小于 root.left.key：LL型，進行右旋

key 大于 root.left.key：LR型，進行左右旋

II.右子樹高

key 大于 root.right.key：RR型，進行左旋

key 小于 root.right.key：RR型，進行右左旋

    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
        if (t == null) {
            return new AVLNode<>(key, value, 1);
        } else if (key.compareTo(t.key) < 0) {
            t.left = insert(t.left, key, value);
            t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
            // 平衡因子判斷
            if (getHeight(t.left) - getHeight(t.right) == 2) {
                if (key.compareTo(root.left.key) < 0) // 左左：右旋
                    t = rightRotate(t);
                else                                 // 左右：先左旋，再右旋
                    t = leftRightRotate(t);
            }
        } else if (key.compareTo(t.key) > 0) {
            t.right = insert(t.right, key, value);
            t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
            // 平衡因子判斷
            if (getHeight(t.left) - getHeight(t.right) == -2) {
                if (key.compareTo(root.right.key) > 0) // 右右：左旋
                    t = leftRotate(t);
                else                                  // 右左：先右旋，再左旋
                    t = rightLeftRotate(t);
            }
        } else {
            t.value = value;
        }
        return t;
    }

刪除算法

概述

可采用二叉查找樹的刪除算法進行刪除。Java數(shù)據(jù)結構之二叉查找樹的實現(xiàn)
刪除某結點 X 后，沿從 X 到根節(jié)點的路徑上考察沿途結點的平衡系數(shù)，若第一個不平衡點為 A，平衡以 A 為根的子樹。
平衡后，可能使子樹 A 高度變小。這樣可能導致 A 的父節(jié)點不滿足平衡性。
所以要繼續(xù)向上考察結點的平衡性，最遠可能至根結點，即最多需要做 O(logn) 次旋轉。
對比“插入”操作：平衡 A 后，子樹高度不變，A 子樹以外的結點不受影響，即插入最多涉及 O(1) 次旋轉。

實例分析

下面舉個刪除的例子：

刪除以下平衡二叉樹中的 16 結點

16 為葉子，將其刪除即可，如下圖。

指針 g 指向實際被刪除節(jié)點 16 之父 25，檢查是否失衡，25 節(jié)點失衡，用 g 、u 、v 記錄失衡三代節(jié)點（從失衡節(jié)點沿著高度大的子樹向下找三代），判斷為 RL 型，進行 RL 旋轉調整平衡，如下圖所示。

繼續(xù)向上檢查，指針 g 指向 g 的雙親 69，檢查是否失衡，69 節(jié)點失衡，用 g 、u 、v 記錄失衡三代節(jié)點，判斷為 RR 型，進行 RR 旋轉調整平衡，如下圖所示。

代碼

代碼描述：

1.若當前結點為空，則返回該節(jié)點

2.若關鍵值小于當前結點的關鍵值，則遞歸處理該結點的左子樹

3.若關鍵值大于當前結點的關鍵值，則遞歸處理該結點的右子樹

4.若關鍵值等于當前結點的關鍵值

若當前結點的左子樹為空，則返回該結點的右子樹根節(jié)點
若當前結點的右子樹為空，則返回該結點的左子樹根節(jié)點
若當前結點左右子樹都不為空，則找到該結點的中序前驅結點（該結點左子樹的最右結點）或中序后繼結點（該結點右子樹的最左結點），將其值賦予該結點，然后遞歸刪除中序前驅或后繼結點。

5.更新結點高度

6.若該結點左子樹高度更高，且處于不平衡狀態(tài)

若為 LL 型，進行右旋
若為 LR 型，先左旋，再右旋

7.若該結點右子樹高度更高，且處于不平衡狀態(tài)

若為 RL 型，先右旋，再左旋
若我 RR 型，進行左旋

8.返回該結點

    public void remove(K key) {
        this.root = delete(root, key);
    }

    public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
        if (t == null) return t;
        if (key.compareTo(t.key) < 0) {
            t.left = delete(t.left, key);
        }
        else if (key.compareTo(t.key) > 0) {
            t.right = delete(t.right, key);
        }
        else {
            if(t.left == null) return t.right;
            else if(t.right == null) return t.left;
            else {         // t.left != null && t.right != null
                AVLNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = delete(t.left, t.key);
            }
        }
        if (t == null) return t;
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        if(getHeight(t.left) - getHeight(t.right) >= 2) {
            if(getHeight(t.left.left) > getHeight(t.left.right)) {
                return rightRotate(t);
            } else {
                return leftRightRotate(t);
            }
        }
        else if(getHeight(t.left) - getHeight(t.right) <= -2) {
            if(getHeight(t.right.left) > getHeight(t.right.right)) {
                return rightLeftRotate(t);
            }
            else {
                return leftRotate(t);
            }
        }
        return t;
    }

完整代碼

class AVLNode<K extends Comparable<K>, V> {
    public K key;
    public V value;
    public int height;
    public AVLNode<K, V> left;
    public AVLNode<K, V> right;

    public AVLNode(K key, V value, int height) {
        this.key = key;
        this.value = value;
        this.height = height;
    }
}

class AVLTree<K extends Comparable<K>, V> {

    public AVLNode<K, V> root;

    public int getHeight(AVLNode<K, V> t) {
        return t == null ? 0 : t.height;
    }

    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    public void remove(K key) {
        this.root = delete(root, key);
    }

    public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
        if (t == null) return t;
        if (key.compareTo(t.key) < 0) {
            t.left = delete(t.left, key);
        }
        else if (key.compareTo(t.key) > 0) {
            t.right = delete(t.right, key);
        }
        else {
            if(t.left == null) return t.right;
            else if(t.right == null) return t.left;
            else {         // t.left != null && t.right != null
                AVLNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = delete(t.left, t.key);
            }
        }
        if (t == null) return t;
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        if(getHeight(t.left) - getHeight(t.right) >= 2) {
            if(getHeight(t.left.left) > getHeight(t.left.right)) {
                return rightRotate(t);
            } else {
                return leftRightRotate(t);
            }
        }
        else if(getHeight(t.left) - getHeight(t.right) <= -2) {
            if(getHeight(t.right.left) > getHeight(t.right.right)) {
                return rightLeftRotate(t);
            }
            else {
                return leftRotate(t);
            }
        }
        return t;
    }


    private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
        if (t == null) {
            return new AVLNode<>(key, value, 1);
        }
        if (key.compareTo(t.key) < 0) {
            t.left = insert(t.left, key, value);
            // 平衡因子判斷
            if (getHeight(t.left) - getHeight(t.right) == 2) {
                if (key.compareTo(t.left.key) < 0) // 左左：右旋
                    t = rightRotate(t);
                else                                  // 左右：先左旋，再右旋
                    t = leftRightRotate(t);
            }
        } else if (key.compareTo(t.key) > 0) {
            t.right = insert(t.right, key, value);
            // 平衡因子判斷
            if (getHeight(t.left) - getHeight(t.right) == -2) {
                if (key.compareTo(t.right.key) > 0) // 右右：左旋
                    t = leftRotate(t);
                else                                   // 右左：先右旋，再左旋
                    t = rightLeftRotate(t);
            }
        } else {
            t.value = value;
        }
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        return t;
    }

    private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
        a.right = rightRotate(a.right);
        return leftRotate(a);
    }

    private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
        a.left = leftRotate(a.left);
        return rightRotate(a);
    }

    private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.right;
        a.right = b.left;
        b.left = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
        return b;
    }

    private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.left;
        a.left = b.right;
        b.right = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
        return b;
    }

    private void inorder(AVLNode<K, V> root) {
        if (root != null) {
            inorder(root.left);
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
            inorder(root.right);
        }
    }

    private void preorder(AVLNode<K, V> root) {
        if (root != null) {
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    private void postorder(AVLNode<K, V> root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
        }
    }

    public void postorderTraverse() {
        System.out.print("后序遍歷：");
        postorder(root);
        System.out.println();
    }

    public void preorderTraverse() {
        System.out.print("先序遍歷：");
        preorder(root);
        System.out.println();
    }

    public void inorderTraverse() {
        System.out.print("中序遍歷：");
        inorder(root);
        System.out.println();
    }
}

方法測試

    public static void main(String[] args) {
        AVLTree<Integer, Integer> tree = new AVLTree<>();
        tree.insert(69, 1);
        tree.insert(25, 1);
        tree.insert(80, 1);
        tree.insert(16, 1);
        tree.insert(56, 1);
        tree.insert(75, 1);
        tree.insert(90, 1);
        tree.insert(30, 1);
        tree.insert(78, 1);
        tree.insert(85, 1);
        tree.insert(98, 1);
        tree.insert(82, 1);

        tree.remove(16);
        tree.preorderTraverse();
        tree.inorderTraverse();
        tree.postorderTraverse();
    }

輸出

先序遍歷：(key: 80 , value: 1 , height: 4) (key: 69 , value: 1 , height: 3) (key: 30 , value: 1 , height: 2) (key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 85 , value: 1 , height: 2) (key: 82 , value: 1 , height: 1) (key: 98 , value: 1 , height: 1)
中序遍歷：(key: 25 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 56 , value: 1 , height: 1) (key: 69 , value: 1 , height: 3) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 80 , value: 1 , height: 4) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 90 , value: 1 , height: 3) (key: 98 , value: 1 , height: 1)
后序遍歷：(key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 69 , value: 1 , height: 3) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 98 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 80 , value: 1 , height: 4)

以上就是Java數(shù)據(jù)結構之平衡二叉樹的實現(xiàn)詳解的詳細內容，更多關于Java平衡二叉樹的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

java基于jdbc實現(xiàn)簡單學生管理系統(tǒng)
本文主要主要介紹了java連接mysql數(shù)據(jù)庫的一個簡單學生系統(tǒng)，通過jdbc連接數(shù)據(jù)庫。文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-10-10
Java動態(tài)調用類中方法代碼
這篇文章主要介紹了Java動態(tài)調用類中方法代碼,需要的朋友可以參考下
2014-02-02
簡單了解JAVA內存泄漏和溢出區(qū)別及聯(lián)系
這篇文章主要介紹了簡單了解JAVA內存泄漏和溢出區(qū)別及聯(lián)系,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-03-03
springboot項目或其他項目使用@Test測試項目接口配置
這篇文章主要介紹了springboot項目或其他項目使用@Test測試項目接口配置,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-07-07
mybatis 加載配置文件的方法（兩種方式）
這篇文章主要介紹了mybatis 加載配置文件的方法，通過實例代碼給大家介紹了mybatis 加載配置文件的兩種方式,需要的朋友可以參考下
2017-12-12
解決idea 拉取代碼出現(xiàn)的 “ Сannot Run Git Cannot identify version of
這篇文章主要介紹了解決idea 拉取代碼出現(xiàn)的 “ Сannot Run Git Cannot identify version of git executable: no response“的問題,需要的朋友可以參考下
2020-08-08
淺談java中replace()和replaceAll()的區(qū)別
這篇文章主要介紹了java中replace()和replaceAll()的區(qū)別，兩者都是常用的替換字符的方法，感興趣的小伙伴們可以參考一下
2015-11-11
23種設計模式（18）java備忘錄模式
這篇文章主要為大家詳細介紹了23種設計模式之java備忘錄模式，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-01-01
Java面試題沖刺第十五天--設計模式
這篇文章主要為大家分享了最有價值的三道關于設計模式的面試題，涵蓋內容全面，包括數(shù)據(jù)結構和算法相關的題目、經(jīng)典面試編程題等，感興趣的小伙伴們可以參考一下
2021-08-08
jsoup?框架的使用小結
jsoup 是一款基于Java的HTML解析器，它提供了一套非常省力的API，不但能直接解析某個URL地址、HTML文本內容，而且還能通過類似于 DOM、CSS 或者jQuery的方法來操作數(shù)據(jù)，所以jsoup也可以被當做爬蟲工具使用，這篇文章主要介紹了jsoup使用,需要的朋友可以參考下
2023-04-04