數據結構之二叉平衡樹

系列文章目錄

數據結構之ArrayList_arraylist o(1) o(n)-CSDN博客

數據結構之LinkedList-CSDN博客

數據結構之棧_棧有什么方法-CSDN博客

數據結構之隊列-CSDN博客

數據結構之二叉樹-CSDN博客

數據結構之優先級隊列-CSDN博客

常見的排序方法-CSDN博客

數據結構之Map和Set-CSDN博客

系列文章目錄

前言

一、二叉搜索樹

1. 二叉搜索樹的性質

2. 二叉搜索樹的查詢性能

二、AVL樹

1. AVL 樹的性質

2. AVL樹的節點定義

3. AVL樹節點的插入

?4. AVL樹的驗證

1. 驗證其為二叉搜索樹

2. 驗證其為平衡樹

5. AVL樹的性能分析

三、紅黑樹

1. 紅黑樹的性質

2. 紅黑樹的節點定義

3. 紅黑樹節點的插入

4. 紅黑樹的驗證

四、AVL樹和紅黑樹的比較

前言

本文介紹了兩種自平衡二叉搜索樹：AVL樹和紅黑樹。AVL樹通過保持左右子樹高度差不超過1來實現嚴格平衡，其查詢效率為O(logN)，但在插入刪除時需要頻繁旋轉調整。紅黑樹通過顏色規則（無連續紅節點、路徑黑節點數相同）實現近似平衡，最長路徑不超過最短路徑兩倍，雖然查詢效率略低于AVL樹，但插入刪除時旋轉次數較少，實際應用更廣泛。文章詳細闡述了兩者的性質、節點結構、插入操作（含平衡調整邏輯）及驗證方法，并通過性能對比說明AVL樹適合讀多寫少場景，紅黑樹更適合頻繁修改的場景。

一、二叉搜索樹

1. 二叉搜索樹的性質

二叉搜索樹中的左孩子的值都小于根節點的值，右孩子的值都大于根節點的值；

二叉搜索樹的中序遍歷是一個有序數組；

2. 二叉搜索樹的查詢性能

如果在二叉搜索樹中連續插入的值都比之前插入的值大，那么二叉搜索樹會變成一棵右單樹，查詢效率就會從原來的 O(logN) 退化成 O(N)；

為了保證二叉搜索樹的查詢效率，就引入了高度平衡的二叉搜索樹，即 AVL 樹；

二、AVL樹

1. AVL 樹的性質

AVL樹是一棵高度平衡的二叉搜索樹，即左右子樹的高度差不超過 1；

2. AVL樹的節點定義

val 表示節點的值；

bf 表示平衡因子，計算方法為 右樹的高度 - 左樹的高度；

left 表示左子樹；

right 表示右子樹；

parent 表示父親節點；

public class AVLTree {static class TreeNode{public int val;public int bf;public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val){this.val = val;}}// 二叉搜索樹的屬性及方法// ......
}

3. AVL樹節點的插入

root 表示 AVL 樹的根節點；

insert(int val): boolean 在 AVL 樹中插入節點；

思路：

1. 如果樹為空，那么新插入的節點就是樹的根節點；

2. 查找

節點的插入方式和二叉搜索樹相同，定義 cur 找要插入節點的位置，parent 指向 cur 的父節點；

如果 cur 的值小于 val，去右子樹找，如果 cur 的值大于 val，去左子樹找找，如果 cur 的值等于 val，說明節點已經存在，不能進行插入，返回 false 即可；?

3. 插入

如果 cur 為空，表示找到了插入位置，如果節點的值小于 parent 的值，插入到 parent 左邊，如果節點的值大于 parent 的值，插入到 parent 的右邊，再讓 cur 重新指向新插入的節點；

4. 修改平衡因子

如果 cur 是 parent 的左子樹，說明插入的節點在 parent 左邊，左子樹的高度增加了，因此 parent 的平衡因子減 1；

如果 cur 是 parent 的右子樹，說明插入的節點在 parent 右邊，右子樹的高度增加了，因此 parent 的平衡因子加 1；

5. 判斷平衡因子

如果修改完 parent 的平衡因子等于 0，表示 parent 這棵樹已經平衡了，同時 0 不會影響整棵樹的平衡，直接返回 true 即可；

如果修改完 parent 的平衡因子等于 1 或者 -1，表示 parent 平衡，但是可能會影響整棵樹的平衡，需要繼續向上調整平衡因子，因此 cur 指向 parent，parent 重新指向 cur 的父節點，繼續向上調整；

6. 樹的調整

繼續向上調整的過程中，如果修改完 parent 的平衡因子等于 2 或者 -2，表示 parent 這棵樹已經不平衡了，此時需要進行旋轉操作，來使得樹重新達到平衡；

如果 parent 的平衡因子等于 2，并且 cur 的平衡因子等于 1，表示 parent 和 cur 子樹的右子樹高度高，此時通過左旋 parent 使樹重新達到平衡；

    private void rotateLeft(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;// 修改四個指向parent.right = subRL;subR.left = parent;if(subRL != null){subRL.parent = parent;}// 修改 parent 的父節點之前，保存 parent 的父節點TreeNode pParent = parent.parent;parent.parent = subR;if(root == parent){root = subR;root.parent = null;}else{if(pParent.left == parent){pParent.left = subR;}else{pParent.right = subR;}}subR.parent = pParent;subR.bf = 0;parent.bf = 0;}

如果 parent 的平衡因子等于 -2，并且 cur 的平衡因子等于 -1，表示 parent 和 cur 子樹的左子樹高度高，此時通過右旋 parent 使樹重新達到平衡；

    private void rotateRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;// 修改四個指向parent.left = subLR;subL.right = parent;if(subLR != null){subLR.parent = parent;}// 記錄父節點的父節點，旋轉完成會用到TreeNode pParent = parent.parent;parent.parent = subL;// 修改 subL 的指向if(root == parent){root = subL;root.parent = null;}else{if(pParent.left == parent){pParent.left = subL;}else{pParent.right = subL;}}subL.parent = pParent;// 修改平衡因子subL.bf = 0;parent.bf = 0;}

如果 parent 的平衡因子等于 2，并且 cur 的平衡因子等于 -1，表示 parent子樹的右子樹高度高，cur 子樹的左子樹高度高，此時通過右旋 cur 子樹，降低 cur 左樹的高度，再左旋 parent 子樹，降低 parent 右樹的高度，使樹重新達到平衡；

    private void rotateRL(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(subR);rotateLeft(parent);if(bf == -1){parent.bf = 0;subRL.bf = 0;subR.bf = 1;}else if(bf == 1){parent.bf = -1;subRL.bf = 0;subR.bf = 0;}}

如果 parent 的平衡因子等于 -2，并且 cur 的平衡因子等于 1，表示 parent子樹的左子樹高度高，cur 子樹的右子樹高度高，此時通過左旋 cur 子樹，降低 cur 右樹的高度，再右旋 parent 子樹，降低 parent 左樹的高度，使樹重新達到平衡；

    private void rotateLR(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;rotateLeft(subL);rotateRight(parent);if(bf == -1){parent.bf = 1;subL.bf = 0;subLR.bf = 0;}else if(bf == 1){subL.bf = -1;subLR.bf = 0;parent.bf = 0;}}

修改平衡因子需要從下往上依次修改，直到 parent 為空；

代碼實現：

    public TreeNode root;public boolean insert(int val){// 1. 插入節點TreeNode node = new TreeNode(val);if(root == null){root = node;return true;}TreeNode parent = null;TreeNode cur = root;while(cur != null){if(cur.val < val){parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur = cur.left;}else{return false;}}// cur == nullif(parent.val < val){parent.right = node;}else{parent.left = node;}node.parent = parent;cur = node;// 2. 平衡因子的修改while(parent != null){if(cur == parent.left){parent.bf--;}else{parent.bf++;}if(parent.bf == 0){return true;}else if(parent.bf == 1 || parent.bf == -1){cur = parent;parent = parent.parent;}else{if(parent.bf == 2){if(cur.bf == 1){// 左單旋rotateLeft(parent);}else{// cur.bf == -1rotateRL(parent);}}else{ // parent.bf == -2if(cur.bf == -1){// 右單旋rotateRight(parent);}else{rotateLR(parent);}}return true;}}return true;}

?4. AVL樹的驗證

1. 驗證其為二叉搜索樹

利用二叉搜索樹的性質：二叉搜索樹的中序遍歷是一個有序數組；

    // 中序遍歷 - 有序表示當前樹是二叉搜索樹public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

2. 驗證其為平衡樹

?如果每一棵子樹都是平衡樹，則這棵樹是平衡樹；

    public int getHeight(TreeNode root){if(root == null) return 0;int left = getHeight(root.left);if(left == -1) return -1;int right = getHeight(root.right);if(right == -1) return -1;if(Math.abs(left - right) > 1) return -1;return Math.max(left, right) + 1;}

5. AVL樹的性能分析

AVL樹是一個高度絕對平衡的二叉搜索樹，查詢的時間復雜度為O(longN)；

當時AVL樹插入或者刪除節點的時候就會涉及到大量的旋轉，性能比較低；

因此 AVL 樹適用于查詢數據，并且這些數據不會被經常修改；

三、紅黑樹

1. 紅黑樹的性質

1. 每個節點不是紅色就是黑色；
2. 根節點是黑色的；
3. 如果一個節點是紅色的，則它的兩個孩子節點是黑色的（沒有兩個連續的紅色節點）；
4. 對于每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點；
5. 每個葉子節點都是黑色的（葉子節點指的是空節點）；

2. 紅黑樹的節點定義

left 表示當前節點的左子樹；

right 表示當前節點的右子樹；

parent 表示當前節點的父親節點；?

val 表示當前節點的值；

color 表示當前節點的顏色；

RBTreeNode(int val)：表示紅黑樹節點的構造方法；

注意：紅黑樹默認插入節點的顏色是紅色的；

如果插入節點是黑色的，為了滿足紅黑樹不同路徑上具有相同數量黑色節點的性質，那么就需要在所有路徑上都插入一個黑色節點，這些節點是沒有意義的，因此默認節點是紅色；

public class RBTree {static class RBTreeNode{public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;public int val;public COLOR color;public RBTreeNode(int val){this.val = val;// 節點默認的顏色為紅色，因為如果插入黑色節點，會導致不同路徑上黑色節點的數量不一樣多，// 這樣還需要插入額外的黑色節點，才能保持紅黑樹的性質this.color = COLOR.RED;}}// 紅黑樹的屬性和方法// ......
}

3. 紅黑樹節點的插入

root 表示紅黑樹的根節點；

insert(int val): boolean 在紅黑樹中插入節點；?

思路：

1. 如果樹為空，那么新插入的節點就是樹的根節點，插入后將根節點的顏色置為黑色；

2. 查找

節點的插入方式和二叉搜索樹相同，定義 cur 找要插入節點的位置，parent 指向 cur 的父節點；

3. 插入

4. 調整顏色

插入一個節點，如果此時插入節點的父親節點也是紅色的，那么就不能滿足紅黑樹不能有兩個連續紅色節點的性質，因此為了解決這個問題，就需要對紅黑樹的顏色進行向上調整；

使用 grandFather 指向?parent 節點的父親節點，uncle 指向 grandFather 的另外一個子節點；

如果 parent 是 grandFather 的左子樹，分為以下三種情況處理：

情況 1：parent 為紅色，uncle 指向 grandFather 的右子樹，且顏色為紅色

parent 和 uncle 調整為黑色，grandFather 調整為紅色，如下所示：

調整完成后 cur 指向 grandFather，parent 指向 cur 的父親節點；?

情況 2：parent 為紅色，uncle 為黑色，grandFather 為黑色，cur 為 parent 的左子樹

先右旋 grandFather，完成后 parent 顏色置為黑色，grandFather 顏色置為紅色，如下圖：

情況 3：parent 為紅色，uncle 為黑色，grandFather 為黑色，cur 為 parent 的右子樹
先左旋 parent，再交換 parent 和 cur 指向的位置，得到的情況和情況 2 是相同的，之后再按照情況的處理方式進行處理即可，如下圖：

同理，如果 parent 是 grandFather 的左子樹，也分為以下三種情況處理：

情況 1：parent 為紅色，uncle 指向 grandFather 的左子樹，且顏色為紅色

parent 和 uncle 調整為黑色，grandFather 調整為紅色，如下所示：

調整完成后 cur 指向 grandFather，parent 指向 cur 的父親節點；?

情況 2：parent 為紅色，uncle 為黑色，grandFather 為黑色，cur 為 parent 的右子樹

先左旋 grandFather，完成后 parent 顏色置為黑色，grandFather 顏色置為紅色，如下圖：

情況 3：parent 為紅色，uncle 為黑色，grandFather 為黑色，cur 為 parent 的左子樹
先右旋 parent，再交換 parent 和 cur 指向的位置，得到的情況和情況 2 是相同的，之后再按照情況的處理方式進行處理即可，如下圖：

5. 處理根節點

向上調整顏色完成后，根節點有可能會被調整為紅色，這是要重新把根節點的顏色調整為黑色，返回 true；?

    public RBTreeNode root;public boolean  insert(int val){RBTreeNode node = new RBTreeNode(val);if(this.root == null){this.root = node;this.root.color = COLOR.BLACK;return true;}RBTreeNode cur = root;RBTreeNode parent = null;while(cur != null){if(cur.val < val){parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur = cur.left;}else{return false;}}// cur == null，找到了應該插入的位置if(parent.val < val){parent.right = node;}else{parent.left = node;}node.parent = parent;cur = node;// 修改顏色while(parent != null && parent.color == COLOR.RED){RBTreeNode grandFather = parent.parent;if(grandFather.left == parent){RBTreeNode uncle = grandFather.right;// 情況 1if(uncle != null && uncle.color == COLOR.RED){parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;cur = grandFather;parent = cur.parent;}else{// parent.color == COLOR.BLANK || uncle.color == COLOR.BLANK// 情況 3：if(parent.right == cur){// 左旋rotateLeft(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}// 情況 2 grandFather.color = COLOR.BLANK uncle.color == COLOR.BLANKrotateRight(grandFather);parent.color = COLOR.BLACK;grandFather.color = COLOR.RED;}}else{// grandFather.right = parentRBTreeNode uncle = grandFather.left;// 情況 1：if(uncle != null && uncle.color == COLOR.RED){parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;cur = grandFather;parent = cur.parent;}else{// parent.color == COLOR.BLANK || uncle.color == COLOR.BLANK// 情況 3：if(parent.left == cur){rotateRight(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}// 情況 2：rotateLeft(grandFather);grandFather.color = COLOR.RED;parent.color = COLOR.BLACK;}}}this.root.color = COLOR.BLACK;return true;}

4. 紅黑樹的驗證

驗證紅黑樹分兩步：

第一步，驗證其為二叉搜索樹，采用中序遍歷的方式

    // 第一步：驗證是否為二叉搜索樹public void inOrder(RBTreeNode root){if(root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

第二步，驗證紅黑樹的性質：

根節點為黑色；
沒有連續的紅色節點；
每條路徑上的黑色節點的數量是相同的；?

    public boolean isRBTree(RBTreeNode root, int pathBlackNum, int blackNum){if(root == null) {return true;}// 驗證紅黑樹的性質，分為三個性質進行驗證// 第一步：驗證根節點是否為黑色if(root.color == COLOR.RED){System.out.println("根節點為紅色！");return false;}boolean flag = false;// 第二步：驗證是否存在連續的兩個紅色的節點flag = checkRedNode(root);if(!flag) return false;// 第三步：驗證是否每條路徑上的黑色節點數量都相同flag = checkBlackNodeNum(root, pathBlackNum, blackNum);if(!flag) return false;return true;}private boolean checkRedNode(RBTreeNode root){if(root == null){return true;}// 遍歷二叉樹，如果遇到紅色的節點，看一下它的父節點是否為紅色即可if(root.color == COLOR.RED){RBTreeNode parent = root.parent;if(parent.color == COLOR.RED){System.out.println("連續兩個紅色的節點！");return false;}}return checkRedNode(root.left) && checkRedNode(root.right);}private boolean checkBlackNodeNum(RBTreeNode root, int pathBlackNum, int blackNum) {if(root == null){if(pathBlackNum == blackNum){return true;}System.out.println("路徑上的黑色節點數量不相同！");return false;}if(root.color == COLOR.BLACK){pathBlackNum++;}return checkBlackNodeNum(root.left, pathBlackNum, blackNum) &&checkBlackNodeNum(root.right, pathBlackNum, blackNum);}