Apa itu AVL Tree?
AVL tree adalah sebuah pohon pencarian biner yang seimbang diri sendiri di mana ketinggian subtree kiri dan kanan dari setiap node berbeda paling banyak satu. Ini berarti bahwa pohon AVL mempertahankan faktor keseimbangan untuk setiap node yang merupakan perbedaan antara tinggi subtree kiri dan tinggi subtree kanannya. Setiap kali sebuah node dimasukkan atau dihapus dari pohon AVL, jika faktor keseimbangan dari suatu node menjadi lebih besar dari satu atau kurang dari minus satu, maka pohon AVL melakukan satu atau lebih rotasi untuk mengembalikan keseimbangan pada pohon. Fitur keseimbangan diri dari AVL tree memastikan kompleksitas waktu operasi pencarian, insert dan delete adalah O(log n) dalam kasus terburuk.
Notes
- AVL tree adalah binary search tree yang bisa menyeimbangkan diri sendiri.
- Ketinggian subtree kiri dan kanan dari setiap node berbeda paling banyak satu.
- AVL tree mempertahankan faktor keseimbangan untuk setiap node.
- Setiap kali sebuah node dimasukkan atau dihapus dari pohon AVL, jika faktor keseimbangan dari suatu node menjadi lebih besar dari satu atau kurang dari minus satu, maka pohon AVL melakukan satu atau lebih rotasi untuk mengembalikan keseimbangan pada pohon.
- Fitur keseimbangan diri dari AVL tree memastikan kompleksitas waktu operasi pencarian, insert dan delete adalah O(log n) dalam kasus terburuk.
- Ketinggian sebuah AVL tree selalu O(log n).
Ilustrasi
Balance Factor = Height of Left Subtree - Height of Right SubtreeDiatas semua node ada angka yang menunjukkan balance factor dari node tersebut, kita tinggal menghitung tinggi pohon kiri dikurangi pohon kanan.
Properti self balancing AVL Tree dipertahankan oleh faktor keseimbangan. Nilai balance factor harus selalu -1, 0 atau +1.
AVL Insert
Disini adalah contoh jika kita memasukkan angka 5 pada AVL Tree, ini sama seperti pada BST Tree.
Selanjutnya kita update semua balance factor pada tree!
Kita bisa lihat bahwa tree tidak seimbang, maka kita lakukan rotasi untuk membuat mereka seimbang.
Hasil akhir berupa AVL Tree yang seimbang lagi (tidak ada balance factor yang 2 keatas).
AVL Delete
Disini kita akan mencoba menghapus node dengan angka 8 pada tree.
Kita harus mencari inorder successor pada tree (algoritmanya sama seperti BST Tree).
Kita copy node inorder successor ke node yang kita mau delete.
Akhirnya tinggal kita delete saja node inorder successor (karena sudah kita copy valuenya ke node 8).
Selanjutnya, seperti biasa kita update lagi balance factor, sehingga kita menemukan bahwa mereka tidak balance (ada yang 2).
Kita lakukan proses rotasi kembali sehingga tree menjadi seimbang lagi.
Implementasi
#include <stdio.h>
#include <stdlib.h>
// AVL tree node structure
struct AVLNode {
int key;
int height;
struct AVLNode* left;
struct AVLNode* right;
};
// Create a new AVL tree node
struct AVLNode* createNode(int key) {
struct AVLNode* newNode = (struct AVLNode*)malloc(sizeof(struct AVLNode));
newNode->key = key;
newNode->height = 1;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Get the height of a node
int getHeight(struct AVLNode* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// Get the balance factor of a node
int getBalance(struct AVLNode* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
// Update the height of a node
void updateHeight(struct AVLNode* node) {
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// Perform a right rotation on a node
struct AVLNode* rotateRight(struct AVLNode* node) {
struct AVLNode* newRoot = node->left;
struct AVLNode* rightChild = newRoot->right;
newRoot->right = node;
node->left = rightChild;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// Perform a left rotation on a node
struct AVLNode* rotateLeft(struct AVLNode* node) {
struct AVLNode* newRoot = node->right;
struct AVLNode* leftChild = newRoot->left;
newRoot->left = node;
node->right = leftChild;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// Insert a key into the AVL tree
struct AVLNode* insert(struct AVLNode* root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
} else {
return root;
}
updateHeight(root);
int balance = getBalance(root);
if (balance > 1 && key < root->left->key) {
return rotateRight(root);
}
if (balance < -1 && key > root->right->key) {
return rotateLeft(root);
}
if (balance > 1 && key > root->left->key) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
if (balance < -1 && key < root->right->key) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
return root;
}
// Get the node with the minimum key in the AVL tree
struct AVLNode* getMinNode(struct AVLNode* root) {
struct AVLNode* current = root;
while (current->left != NULL) {
current = current->left;
}
return current;
}
// Delete a key from the AVL tree
struct AVLNode* delete(struct AVLNode* root, int key) {
if (root == NULL) {
return root;
} else if (key < root->key) {
root->left = delete(root->left, key);
} else if (key > root->key) {
root->right = delete(root->right, key);
} else {
if (root->left == NULL || root->right == NULL) {
struct AVLNode* temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else {
*root = *temp;
}
free(temp);
} else {
struct AVLNode* temp = getMinNode(root->right);
root->key = temp->key;
root->right = delete(root->right, temp->key);
}
}
if (root == NULL) {
return root;
}
updateHeight(root);
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0) {
return rotateRight(root);
}
if (balance > 1 && getBalance(root->left) < 0) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
if (balance < -1 && getBalance(root->right) <= 0) {
return rotateLeft(root);
}
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
return root;
}
// Search for a key in the AVL tree
struct AVLNode* search(struct AVLNode* root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
}
return search(root->right, key);
}
// Print the inorder traversal of the AVL tree
void printInorder(struct AVLNode* root) {
if (root != NULL) {
printInorder(root->left);
printf("%d ", root->key);
printInorder(root->right);
}
}
int main() {
struct AVLNode* root = NULL;
// Insert nodes into the AVL tree
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
// Print the inorder traversal of the AVL tree
printf("Inorder traversal of the AVL tree: ");
printInorder(root);
printf("\n");
// Search for nodes in the AVL tree
struct AVLNode* node1 = search(root, 30);
struct AVLNode* node2 = search(root, 25);
if (node1 == NULL) {
printf("Node with key 30 not found in the AVL tree.\n");
} else {
printf("Node with key 30 found in the AVL tree.\n");
}
if (node2 == NULL) {
printf("Node with key 25 not found in the AVL tree.\n");
} else {
printf("Node with key 25 found in the AVL tree.\n");
}
// Delete nodes from the AVL tree
root = delete(root, 30);
root = delete(root, 40);
// Print the inorder traversal of the AVL tree
printf("Inorder traversal of the AVL tree after deletion: ");
printInorder(root);
printf("\n");
return 0;
}Output
Inorder traversal of the AVL tree: 10 20 25 30 40 50
Node with key 30 found in the AVL tree.
Node with key 25 found in the AVL tree.
Inorder traversal of the AVL tree after deletion: 10 20 25 50