AVL樹
AVL樹是最早提出的自平衡二元搜尋樹。它通過維護每個節點的平衡因子(左子樹高度減去右子樹高度)。
在每次插入或刪除操作後進行調整,以確保樹保持平衡。
AVL 樹由 Georgy Adelson-Velsky 和 Evgenii Landis 於 1962 年提出的一種自平衡二元搜尋樹。
它的平衡性通過維護每個節點的平衡因子(Balance Factor)來確保,該平衡因子表示左子樹高度減去右子樹高度的差值。
當在AVL樹中進行插入或刪除操作時,可能會破壞樹的平衡。
在這種情況下,需要通過旋轉操作來恢復平衡。旋轉操作分為左旋和右旋兩種:
- 左旋:當某個節點的右子樹高度過高時,進行左旋操作可以降低右子樹高度,同時提升該節點的左子樹高度。
- 右旋:當某個節點的左子樹高度過高時,進行右旋操作可以降低左子樹高度,同時提升該節點的右子樹高度。
這些旋轉操作的目的是保持樹的平衡,使得樹的高度始終保持在O(log n)的範圍內。儘管AVL樹提供了較嚴格的平衡性,但相對而言,它需要更多的旋轉操作,因此插入和刪除的成本較高。
以下是 AVL 樹進行平衡的規則
AVL 樹在插入或刪除節點後,可能會失去平衡,也就是某些節點的左子樹和右子樹的高度差超過 1。為了維護 AVL 樹的平衡性,我們需要進行旋轉操作。
- 左旋轉(Left Rotation):
- 條件:當一個節點的右子樹比左子樹高度多 2 層或以上時,我們進行左旋轉操作。
- 作法:左旋轉可以將該節點的右子樹提升為新的根節點,同時將原根節點降低為新根節點的左子樹。這樣可以保持左子樹和右子樹的高度差不超過 1。
- 右旋轉(Right Rotation):
- 條件:當一個節點的左子樹比右子樹高度多 2 層或以上時,我們進行右旋轉操作。
- 作法:右旋轉可以將該節點的左子樹提升為新的根節點,同時將原根節點降低為新根節點的右子樹。這樣可以保持左子樹和右子樹的高度差不超過 1。
- 左右旋轉(Left-Right Rotation):
- 條件:當一個節點的左子樹比右子樹高度多,且該節點的左子樹的右子樹比左子樹的左子樹高度多時,我們進行左右旋轉操作。
- 作法:先對該節點的左子節點進行左旋轉,然後對原節點進行右旋轉。
- 右左旋轉(Right-Left Rotation):
- 條件:當一個節點的右子樹比左子樹高度多,且該節點的右子樹的左子樹比右子樹的右子樹高度多時,我們進行右左旋轉操作。
- 作法:先對該節點的右子節點進行右旋轉,然後對原節點進行左旋轉。
這些旋轉操作可以調整 AVL 樹的結構,使其保持平衡。在進行插入或刪除操作後,我們需要檢查節點的平衡因子,即左子樹高度減去右子樹高度。
- 如果平衡因子大於 1,表示左子樹高於右子樹,則需要進行右旋轉或左右旋轉;
- 如果平衡因子小於 -1,表示右子樹高於左子樹,則需要進行左旋轉或右左旋轉。
通過這些旋轉操作,我們可以保持 AVL 樹的平衡性。
實作
class AVLNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVLTree {
constructor() {
this.root = null;
}
// Helper function to get the height of a node
getHeight(node) {
if (node === null) return 0;
return node.height;
}
// Helper function to update the height of a node
updateHeight(node) {
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
}
// Helper function to perform left rotation
leftRotate(z) {
const y = z.right;
const T2 = y.left;
y.left = z;
z.right = T2;
this.updateHeight(z);
this.updateHeight(y);
return y;
}
// Helper function to perform right rotation
rightRotate(z) {
const y = z.left;
const T3 = y.right;
y.right = z;
z.left = T3;
this.updateHeight(z);
this.updateHeight(y);
return y;
}
// Helper function to get the balance factor of a node
getBalanceFactor(node) {
if (node === null) return 0;
return this.getHeight(node.left) - this.getHeight(node.right);
}
// Helper function to insert a value into the AVL tree
insertHelper(node, value) {
if (node === null) {
return new AVLNode(value);
}
if (value < node.value) {
node.left = this.insertHelper(node.left, value);
} else if (value > node.value) {
node.right = this.insertHelper(node.right, value);
} else {
// Duplicate values are not allowed in AVL tree
return node;
}
this.updateHeight(node);
const balanceFactor = this.getBalanceFactor(node);
// Left Left Case
if (balanceFactor > 1 && value < node.left.value) {
return this.rightRotate(node);
}
// Right Right Case
if (balanceFactor < -1 && value > node.right.value) {
return this.leftRotate(node);
}
// Left Right Case
if (balanceFactor > 1 && value > node.left.value) {
node.left = this.leftRotate(node.left);
return this.rightRotate(node);
}
// Right Left Case
if (balanceFactor < -1 && value < node.right.value) {
node.right = this.rightRotate(node.right);
return this.leftRotate(node);
}
return node;
}
// Function to insert a value into the AVL tree
insert(value) {
this.root = this.insertHelper(this.root, value);
}
}
參考資料
- 👍 大力推薦參考圖文並茂超完整圖解何時該左旋何時該右旋【JavaScript 學演算法(十五)- AVL-Tree】
最後,如果你覺得我的分享對你有幫助,請給予我一個愛心,並且分享這篇文章,這將是對我最大的鼓勵!