AVL Tree
Terakhir diperbarui
AVL tree adalah binary search tree yang menyeimbangkan dirinya sendiri (self-balancing). Cara kerjanya seperti BST biasa, tetapi setelah setiap penyisipan, AVL tree memeriksa balance factor setiap leluhur, yaitu selisih tinggi antara subtree kiri dan kanannya. Jika ada node yang menjadi tidak seimbang (selisihnya lebih dari 1), pohon melakukan rotasi untuk memulihkan keseimbangan. Tekan Putar di atas untuk melihat nilai disisipkan dan pohon berotasi kembali ke bentuknya.
Karena pohon tidak pernah dibiarkan lebih dari sedikit miring, AVL tree menjamin tinggi O(log n), sehingga pencarian, penyisipan, dan penghapusan selalu O(log n), bahkan untuk input terurut yang akan merusak BST biasa. Harganya adalah rotasi tambahan dan pencatatan tinggi pada setiap penyisipan.
Kompleksitas waktu dan ruang
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Pencarian | O(log n) | Tinggi selalu ~1,44 log n |
| Penyisipan | O(log n) | Ditambah O(1) rotasi |
| Penghapusan | O(log n) | Ditambah O(log n) rotasi |
| Ruang | O(n) | Satu field tinggi per node |
Empat kasus rotasi
| Kasus | Ketidakseimbangan | Perbaikan |
|---|---|---|
| Left-Left | Berat di kiri dari anak kiri | Satu rotasi kanan |
| Right-Right | Berat di kanan dari anak kanan | Satu rotasi kiri |
| Left-Right | Berat di kanan dari anak kiri | Rotasi kiri, lalu rotasi kanan |
| Right-Left | Berat di kiri dari anak kanan | Rotasi kanan, lalu rotasi kiri |
Contoh penerapan
Menyisipkan [10, 20, 30, 40, 50, 25] satu nilai demi satu nilai:
| Langkah | Struktur | Aksi |
|---|---|---|
Sisipkan 10 | 10 | Node pertama menjadi root; seimbang |
Sisipkan 20 | 10(_, 20) | Masuk ke kanan 10; masih seimbang |
Sisipkan 30 | 20(10, 30) | Right-Right di 10, jadi satu rotasi kiri mengangkat 20 menjadi root |
Sisipkan 40 | 20(10, 30(_, 40)) | Masuk ke kanan 30; setiap balance factor tetap dalam ±1 |
Sisipkan 50 | 20(10, 40(30, 50)) | Right-Right di 30, jadi rotasi kiri di 30 mengangkat 40 |
Sisipkan 25 | 30(20(10, 25), 40(_, 50)) | Right-Left di 20: rotasi kanan pada subtree 40, lalu rotasi kiri pada 20 |
Kapan memakai AVL tree
| Pakai saat | Hindari saat |
|---|---|
| Pencarian jauh lebih sering daripada penyisipan dan kamu ingin tinggi pohon serendah mungkin | Penyisipan dan penghapusan mendominasi: rotasi dan penyeimbangan ulang tambahannya lebih mahal daripada red-black tree |
Kamu butuh kasus terburuk O(log n) yang terjamin, bahkan untuk input yang sengaja buruk atau sudah terurut | Hash table biasa sudah cukup: kamu tidak butuh penelusuran berurutan atau range query |
| Kamu butuh operasi berurutan: penelusuran in-order, predecessor/successor, range query | Datanya sangat kecil: BST biasa atau array terurut lebih sederhana dan sudah cukup cepat |
| Data mungkin datang dalam keadaan terurut, yang akan mengubah BST tak seimbang menjadi linked list | Kamu tidak sanggup menanggung memori tambahan untuk field tinggi di setiap node karena ruang yang sangat terbatas |
Kode AVL Tree
Implementasi AVL Tree yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode AVL Tree dalam Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Kode AVL Tree dalam JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Kode AVL Tree dalam Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Kode AVL Tree dalam C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Kode AVL Tree dalam C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}FAQ AVL Tree
Apa itu balance factor pada AVL tree?
Balance factor sebuah node adalah tinggi subtree kirinya dikurangi tinggi subtree kanannya. AVL tree menjaga balance factor setiap node di -1, 0, atau +1; jika sebuah penyisipan membuatnya keluar dari rentang itu, rotasi akan memulihkan keseimbangan.
Apa perbedaan AVL tree dan red-black tree?
Keduanya adalah BST yang menyeimbangkan diri dengan operasi
O(log n). AVL tree diseimbangkan lebih ketat, jadi pencarian sedikit lebih cepat, tetapi bisa melakukan lebih banyak rotasi saat penyisipan/penghapusan. Red-black tree diseimbangkan lebih longgar dan mengutamakan rotasi yang lebih sedikit. Itulah sebabnya banyak library standar memakainya untuk map dan set.Mengapa memakai AVL tree, bukan binary search tree biasa?
BST biasa bisa merosot menjadi operasi
O(n) jika nilai datang dalam urutan terurut sehingga membentuk rantai yang miring. AVL tree berotasi agar tetap seimbang, sehingga menjamin tinggi dan operasi O(log n) apa pun urutan penyisipannya.Apakah AVL tree lebih baik daripada red-black tree untuk indeks database?
Tergantung beban kerjanya. AVL tree diseimbangkan lebih kaku, jadi unggul saat pembacaan mendominasi dan kamu ingin jalur pencarian sependek mungkin. Namun, sebagian besar database dan library bahasa memilih red-black tree (atau B-tree) karena keduanya menyeimbangkan ulang dengan rotasi yang lebih sedikit pada beban kerja yang banyak menulis, dan hal itu lebih penting saat penyisipan dan penghapusan sering terjadi.
Berapa banyak rotasi yang dibutuhkan satu penyisipan AVL?
Paling banyak satu rotasi, entah rotasi tunggal atau rotasi ganda (dua langkah), untuk menyeimbangkan ulang pohon setelah menyisipkan satu nilai. Itu karena penyisipan menambah tinggi sebuah subtree paling banyak satu, jadi satu perbaikan di leluhur tak seimbang yang paling bawah sudah cukup. Penghapusan berbeda: bisa membutuhkan hingga
O(log n) rotasi karena penyeimbangan ulang merambat ke arah root.Apakah tinggi node perlu diperbarui setelah setiap rotasi?
Ya. Bug yang umum adalah memutar pointer dengan benar tetapi lupa menghitung ulang tinggi dua node yang terlibat. Setelah setiap rotasi, kamu harus memperbarui tinggi node yang diturunkan terlebih dahulu, lalu node yang dinaikkan, karena tinggi node yang dinaikkan bergantung pada anak-anak barunya. Jika langkah ini dilewati, balance factor menjadi usang dan merusak keputusan penyeimbangan berikutnya.
Sumber terkait
Visualisasi lainnya
