Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的實(shí)現(xiàn)詳解
定義
動(dòng)機(jī)：二叉查找樹的操作實(shí)踐復(fù)雜度由樹高度決定，所以希望控制樹高，左右子樹盡可能平衡。
平衡二叉樹（AVL樹）：稱一棵二叉查找樹為高度平衡樹，當(dāng)且僅當(dāng)或由單一外結(jié)點(diǎn)組成，或由兩個(gè)子樹形 Ta 和 Tb 組成，并且滿足：
- |h(Ta) - h(Tb)| <= 1，其中 h(T) 表示樹 T 的高度
- Ta 和 Tb 都是高度平衡樹
即：每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度最多差 1 的 二叉查找樹。
- 設(shè) T 為高度平衡樹中結(jié)點(diǎn) q 的平衡系數(shù)為 q 的右子樹高度減去左子樹高度
- 高度平衡樹所以結(jié)點(diǎn)的平衡系數(shù)只可能為：-1, 0, 1
結(jié)點(diǎn)結(jié)構(gòu)
key：關(guān)鍵字的值
value：關(guān)鍵字的存儲(chǔ)信息
height：樹的高度（只有一個(gè)結(jié)點(diǎn)的樹的高度為 1）
left：左子樹根結(jié)點(diǎn)的的引用
right：右子樹根結(jié)點(diǎn)的引用
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ù)結(jié)構(gòu)之二叉查找樹的實(shí)現(xiàn)
插入算法
AVL 樹是一種二叉查找樹，故可以使用二叉查找樹的插入方法插入結(jié)點(diǎn)，但插入一個(gè)新結(jié)點(diǎn)時(shí)，有可能破壞 AVL 樹的平衡性。
如果發(fā)生這種情況，就需要在插入結(jié)點(diǎn)后對(duì)平衡樹進(jìn)行調(diào)整，恢復(fù)平衡的性質(zhì)。實(shí)現(xiàn)這種調(diào)整的操作稱為“旋轉(zhuǎn)”。
在插入一個(gè)新結(jié)點(diǎn) X 后，應(yīng)調(diào)整失去平衡的最小子樹，即從插入點(diǎn)到根的路徑向上找第一個(gè)不平衡結(jié)點(diǎn) A。
平衡因子：該結(jié)點(diǎn)的左子樹高度和右子樹高度的差值。如果差值的絕對(duì)值小于等于 1，則說明該結(jié)點(diǎn)平衡，如果差值的絕對(duì)值為 2（不會(huì)出現(xiàn)其他情況），則說明該結(jié)點(diǎn)不平衡，需要做平衡處理。
造成結(jié)點(diǎn) A 不平衡的的原因以及調(diào)整方式有以下幾種情況。
LL 型
A 結(jié)點(diǎn)的平衡因子為 2，說明該結(jié)點(diǎn)是最小不平衡結(jié)點(diǎn)，需要對(duì) A 結(jié)點(diǎn)進(jìn)行調(diào)整。問題發(fā)生在 A 結(jié)點(diǎn)左子結(jié)點(diǎn)的左子結(jié)點(diǎn)，所以為 LL 型。
扁擔(dān)原理：右旋
- 將 A 的左孩子 B 提升為新的根結(jié)點(diǎn)；
- 將原來的根結(jié)點(diǎn) A 降為 B 的右孩子；
- 各子樹按大小關(guān)系連接(BL 和 AR 不變，BR 調(diào)整為 A 的左子樹)。
- 高度調(diào)整：由于調(diào)整后 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 結(jié)點(diǎn)的平衡因子為 2，說明該結(jié)點(diǎn)是最小不平衡結(jié)點(diǎn)，需要對(duì) A 結(jié)點(diǎn)進(jìn)行調(diào)整。問題發(fā)生在 A 結(jié)點(diǎn)右子結(jié)點(diǎn)的右子結(jié)點(diǎn)，所以為 RR 型。
扁擔(dān)原理：左旋
- 將 A 的右孩子 B 提升為新的根結(jié)點(diǎn)；
- 將原來的根結(jié)點(diǎn) A 降為 B 的左孩子；
- 各子樹按大小關(guān)系連接(AL 和 BR 不變，BL 調(diào)整為 A 的右子樹)。
- 高度調(diào)整：由于調(diào)整后 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 結(jié)點(diǎn)的平衡因子為 2，說明該結(jié)點(diǎn)是最小不平衡結(jié)點(diǎn)，需要對(duì) A 結(jié)點(diǎn)進(jìn)行調(diào)整。問題發(fā)生在 A 結(jié)點(diǎn)左子結(jié)點(diǎn)的右子結(jié)點(diǎn)，所以為 LR 型。
- 從旋轉(zhuǎn)的角度：對(duì) B 左旋，然后對(duì) A 右旋
- 將 B 的左孩子 C 提升為新的根結(jié)點(diǎn)；
- 將原來的根結(jié)點(diǎn) A 降為 C 的右孩子；
- 各子樹按大小關(guān)系連接(BL 和 AR 不變，CL 和 CR 分別調(diào)整為 B 的右子樹和 A 的左子樹)。
private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
a.left = leftRotate(a.left); // 對(duì) B 左旋
return rightRotate(a); // 對(duì) A 右旋
}
RL 型
A 結(jié)點(diǎn)的平衡因子為 2，說明該結(jié)點(diǎn)是最小不平衡結(jié)點(diǎn)，需要對(duì) A 結(jié)點(diǎn)進(jìn)行調(diào)整。問題發(fā)生在 A 結(jié)點(diǎn)右子結(jié)點(diǎn)的左子結(jié)點(diǎn)，所以為 RL 型。
- 從旋轉(zhuǎn)的角度：對(duì) B 右旋，然后對(duì) A 左旋
- 將 B 的左孩子 C 提升為新的根結(jié)點(diǎn)；
- 將原來的根結(jié)點(diǎn) A 降為 C 的左孩子；
- 各子樹按大小關(guān)系連接(AL 和 BR 不變，CL 和 CR 分別調(diào)整為 A 的右子樹和 B 的左子樹)。
private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
a.right = rightRotate(a.right);
return leftRotate(a);
}
插入方法
根結(jié)點(diǎn)默認(rèn)高度為 1
某結(jié)點(diǎn)的左右子樹高度差的絕對(duì)值為 2，則需要進(jìn)行平衡處理
I.左子樹高
key 小于 root.left.key：LL型，進(jìn)行右旋
key 大于 root.left.key：LR型，進(jìn)行左右旋
II.右子樹高
key 大于 root.right.key：RR型，進(jìn)行左旋
key 小于 root.right.key：RR型，進(jìn)行右左旋
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;
}
刪除算法
概述
- 可采用二叉查找樹的刪除算法進(jìn)行刪除。Java數(shù)據(jù)結(jié)構(gòu)之二叉查找樹的實(shí)現(xiàn)
- 刪除某結(jié)點(diǎn) X 后，沿從 X 到根節(jié)點(diǎn)的路徑上考察沿途結(jié)點(diǎn)的平衡系數(shù)，若第一個(gè)不平衡點(diǎn)為 A，平衡以 A 為根的子樹。
- 平衡后，可能使子樹 A 高度變小。這樣可能導(dǎo)致 A 的父節(jié)點(diǎn)不滿足平衡性。
- 所以要繼續(xù)向上考察結(jié)點(diǎn)的平衡性，最遠(yuǎn)可能至根結(jié)點(diǎn)，即最多需要做
O(logn)次旋轉(zhuǎn)。 - 對(duì)比“插入”操作：平衡 A 后，子樹高度不變，A 子樹以外的結(jié)點(diǎn)不受影響，即插入最多涉及
O(1)次旋轉(zhuǎn)。
實(shí)例分析
下面舉個(gè)刪除的例子：
刪除以下平衡二叉樹中的 16 結(jié)點(diǎn)
16 為葉子，將其刪除即可，如下圖。
指針 g 指向?qū)嶋H被刪除節(jié)點(diǎn) 16 之父 25，檢查是否失衡，25 節(jié)點(diǎn)失衡，用 g 、u 、v 記錄失衡三代節(jié)點(diǎn)（從失衡節(jié)點(diǎn)沿著高度大的子樹向下找三代），判斷為 RL 型，進(jìn)行 RL 旋轉(zhuǎn)調(diào)整平衡，如下圖所示。
繼續(xù)向上檢查，指針 g 指向 g 的雙親 69，檢查是否失衡，69 節(jié)點(diǎn)失衡，用 g 、u 、v 記錄失衡三代節(jié)點(diǎn)，判斷為 RR 型，進(jìn)行 RR 旋轉(zhuǎn)調(diào)整平衡，如下圖所示。
代碼
代碼描述：
1.若當(dāng)前結(jié)點(diǎn)為空， 則返回該節(jié)點(diǎn)
2.若關(guān)鍵值小于當(dāng)前結(jié)點(diǎn)的關(guān)鍵值，則遞歸處理該結(jié)點(diǎn)的左子樹
3.若關(guān)鍵值大于當(dāng)前結(jié)點(diǎn)的關(guān)鍵值，則遞歸處理該結(jié)點(diǎn)的右子樹
4.若關(guān)鍵值等于當(dāng)前結(jié)點(diǎn)的關(guān)鍵值
- 若當(dāng)前結(jié)點(diǎn)的左子樹為空，則返回該結(jié)點(diǎn)的右子樹根節(jié)點(diǎn)
- 若當(dāng)前結(jié)點(diǎn)的右子樹為空，則返回該結(jié)點(diǎn)的左子樹根節(jié)點(diǎn)
- 若當(dāng)前結(jié)點(diǎn)左右子樹都不為空，則找到該結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)（該結(jié)點(diǎn)左子樹的最右結(jié)點(diǎn)）或中序后繼結(jié)點(diǎn)（該結(jié)點(diǎn)右子樹的最左結(jié)點(diǎn)），將其值賦予該結(jié)點(diǎn)，然后遞歸刪除中序前驅(qū)或后繼結(jié)點(diǎn)。
5.更新結(jié)點(diǎn)高度
6.若該結(jié)點(diǎn)左子樹高度更高，且處于不平衡狀態(tài)
- 若為 LL 型，進(jìn)行右旋
- 若為 LR 型，先左旋，再右旋
7.若該結(jié)點(diǎn)右子樹高度更高，且處于不平衡狀態(tài)
- 若為 RL 型，先右旋，再左旋
- 若我 RR 型，進(jìn)行左旋
8.返回該結(jié)點(diǎn)
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();
}
}
方法測(cè)試
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ù)結(jié)構(gòu)之平衡二叉樹的實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于Java平衡二叉樹的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
java基于jdbc實(shí)現(xiàn)簡單學(xué)生管理系統(tǒng)
本文主要主要介紹了java連接mysql數(shù)據(jù)庫的一個(gè)簡單學(xué)生系統(tǒng)，通過jdbc連接數(shù)據(jù)庫。文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
Java動(dòng)態(tài)調(diào)用類中方法代碼
這篇文章主要介紹了Java動(dòng)態(tài)調(diào)用類中方法代碼,需要的朋友可以參考下2014-02-02
簡單了解JAVA內(nèi)存泄漏和溢出區(qū)別及聯(lián)系
這篇文章主要介紹了簡單了解JAVA內(nèi)存泄漏和溢出區(qū)別及聯(lián)系,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
springboot項(xiàng)目或其他項(xiàng)目使用@Test測(cè)試項(xiàng)目接口配置
這篇文章主要介紹了springboot項(xiàng)目或其他項(xiàng)目使用@Test測(cè)試項(xiàng)目接口配置,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-07-07
這篇文章主要介紹了mybatis 加載配置文件的方法，通過實(shí)例代碼給大家介紹了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
這篇文章主要為大家詳細(xì)介紹了23種設(shè)計(jì)模式之java備忘錄模式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要為大家分享了最有價(jià)值的三道關(guān)于設(shè)計(jì)模式的面試題，涵蓋內(nèi)容全面，包括數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目、經(jīng)典面試編程題等，感興趣的小伙伴們可以參考一下2021-08-08
jsoup 是一款基于Java的HTML解析器，它提供了一套非常省力的API，不但能直接解析某個(gè)URL地址、HTML文本內(nèi)容，而且還能通過類似于 DOM、CSS 或者jQuery的方法來操作數(shù)據(jù)，所以jsoup也可以被當(dāng)做爬蟲工具使用，這篇文章主要介紹了jsoup使用,需要的朋友可以參考下2023-04-04