Java數(shù)據(jù)結構之平衡二叉樹的實現(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平衡二叉樹的資料請關注腳本之家其它相關文章！
相關文章
Spring框架基于注解的AOP之各種通知的使用與環(huán)繞通知實現(xiàn)詳解
這篇文章主要介紹了Spring框架基于注解的AOP之各種通知的使用及其環(huán)繞通知，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-11-11
解析springBoot-actuator項目構造中health端點工作原理
這篇文章主要介紹了springBoot-actuator中health端點工作原理，對spring-boot-actuator的項目構造，工作原理進行了全面的梳理，側重health健康檢查部分2022-02-02
Swagger是一個規(guī)范和完整的框架,用于生成、描述、調用和可視化Restful風格的Web服務,這篇文章主要給大家介紹了關于SpringBoot中使用Swagger的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-12-12
SpringBoot如何注冊Servlet、Filter、Listener的幾種方式
在Servlet 3.0之前都是使用web.xml文件進行配置，這篇文章主要介紹了SpringBoot如何注冊Servlet、Filter、Listener的幾種方式,在Servlet 3.0之前都是使用web.xml文件進行配置，2018-10-10
這篇文章主要介紹了Jax-rs規(guī)范下REST接口使用方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09
這篇文章主要介紹了Java計算程序代碼執(zhí)行時間的方法,結合實例形式總結分析了java采用毫秒數(shù)及納秒數(shù)計算程序運行時間的相關操作技巧,需要的朋友可以參考下2017-11-11
在Java中，final關鍵字可以用來修飾類、方法和變量（包括成員變量和局部變量)，下面通過本篇文章給大家介紹java中的final關鍵字，對java fina關鍵字相關知識感興趣的朋友一起看看吧2015-12-12
SpringBoot實現(xiàn)devtools實現(xiàn)熱部署過程解析
這篇文章主要介紹了SpringBoot實現(xiàn)devtools實現(xiàn)熱部署過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
使用Swagger2實現(xiàn)自動生成RESTful?API文檔
在開發(fā)?RESTful?API?的過程中，文檔是非常重要的一部分，可以幫助開發(fā)者了解?API?的功能和使用方法，本文將使用Swagger2?實現(xiàn)自動生成?RESTful?API?文檔，需要的可以參考一下2023-06-06
Java Jedis NOAUTH Authentication required問題解決方法
這篇文章主要介紹了Java Jedis NOAUTH Authentication required問題解決方法,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07