Binary Search Tree vs AVL Tree: Perbedaan dan Kapan Menggunakannya
Pendahuluan
Saat membangun fitur pencarian atau pengurutan data, dua struktur data yang sering menjadi pilihan developer adalah Binary Search Tree (BST) dan AVL Tree. Keduanya termasuk dalam kategori tree (pohon), namun punya karakteristik dan kasus penggunaan yang berbeda.
Kamu mungkin sudah familiar dengan konsep dasar tree dari artikel Tutorial Tree (Pohon) dalam Struktur Data untuk Pemula. Di artikel ini, kita akan masuk lebih dalam: membedah cara kerja BST, memahami mengapa AVL Tree lahir, dan yang paling penting — kapan menggunakan masing-masing.
Membedah Binary Search Tree (BST)
BST adalah tree di mana setiap node mengikuti satu aturan sederhana: nilai kiri < node < nilai kanan. Aturan ini membuat pencarian data menjadi sangat efisien karena kamu bisa “memangkas” setengah dari kemungkinan di setiap langkah.
Implementasi BST dalam Python
class Node:
def __init__(self, value):
self.value = value
self.left = None # Anak kiri untuk nilai yang lebih kecil
self.right = None # Anak kanan untuk nilai yang lebih besar atau sama
class BST:
def __init__(self):
self.root = None # Root awalnya kosong
def insert(self, value):
# Jika tree masih kosong, jadikan nilai ini sebagai root
if self.root is None:
self.root = Node(value)
return
self._insert_recursive(self.root, value)
def _insert_recursive(self, node, value):
# Masukkan ke subtree kiri jika nilainya lebih kecil
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self._insert_recursive(node.left, value)
else:
# Selain itu, masukkan ke subtree kanan
if node.right is None:
node.right = Node(value)
else:
self._insert_recursive(node.right, value)
def search(self, value):
# Mulai pencarian dari root
return self._search_recursive(self.root, value)
def _search_recursive(self, node, value):
# Jika node tidak ada, berarti nilai tidak ditemukan
if node is None:
return False
# Jika nilai cocok, kembalikan True
if node.value == value:
return True
# Cari ke kiri jika nilai lebih kecil
if value < node.value:
return self._search_recursive(node.left, value)
# Jika tidak, cari ke kanan
return self._search_recursive(node.right, value)
# Contoh penggunaan
bst = BST()
# Data dimasukkan satu per satu ke dalam BST
for val in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(val)
# Mencari beberapa nilai di dalam tree
print(bst.search(40))
print(bst.search(99))
# Output yang diharapkan:
# > True
# > FalseMasalah Utama BST: Skewed Tree
BST bekerja baik saat data masuk secara acak. Tapi bayangkan kamu menyisipkan data yang sudah terurut: 1, 2, 3, 4, 5. Hasilnya adalah skewed tree — pohon yang condong ke satu sisi seperti linked list.
1
\
2
\
3
\
4
\
5Akibatnya, kompleksitas operasi yang seharusnya O(log n) berubah menjadi O(n) — persis seperti linear search biasa. Inilah kelemahan fatal BST yang dipecahkan oleh AVL Tree.
Mengenal AVL Tree: Si Penjaga Keseimbangan
AVL Tree (dinamai dari penemunya: Adelson-Velsky dan Landis) adalah BST yang menjaga keseimbangannya secara otomatis. Ia menggunakan konsep balance factor untuk memastikan perbedaan tinggi antara subtree kiri dan kanan tidak melebihi 1.
Balance Factor = height(left subtree) - height(right subtree)
Nilai valid: -1, 0, atau +1Jika balance factor melebihi rentang ini setelah operasi insert atau delete, AVL Tree melakukan rotasi untuk menyeimbangkan diri kembali.
Empat Jenis Rotasi AVL
| Kasus | Rotasi |
|---|---|
| Left-Left (LL) | Right Rotation |
| Right-Right (RR) | Left Rotation |
| Left-Right (LR) | Left-Right Rotation |
| Right-Left (RL) | Right-Left Rotation |
Implementasi AVL Tree dalam Python
class AVLNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1 # Node baru selalu memiliki tinggi 1
class AVLTree:
def height(self, node):
return node.height if node else 0
def balance_factor(self, node):
# Selisih tinggi subtree kiri dan kanan
return self.height(node.left) - self.height(node.right)
def update_height(self, node):
# Tinggi node = 1 + tinggi maksimum dari dua anaknya
node.height = 1 + max(self.height(node.left), self.height(node.right))
def rotate_right(self, y):
# Rotasi kanan untuk menangani kasus tidak seimbang di kiri
x = y.left
t2 = x.right
x.right = y
y.left = t2
self.update_height(y)
self.update_height(x)
return x
def rotate_left(self, x):
# Rotasi kiri untuk menangani kasus tidak seimbang di kanan
y = x.right
t2 = y.left
y.left = x
x.right = t2
self.update_height(x)
self.update_height(y)
return y
def balance(self, node):
# Perbarui tinggi lalu cek keseimbangan node
self.update_height(node)
bf = self.balance_factor(node)
# Kasus Left-Left
if bf > 1 and self.balance_factor(node.left) >= 0:
return self.rotate_right(node)
# Kasus Left-Right
if bf > 1 and self.balance_factor(node.left) < 0:
node.left = self.rotate_left(node.left)
return self.rotate_right(node)
# Kasus Right-Right
if bf < -1 and self.balance_factor(node.right) <= 0:
return self.rotate_left(node)
# Kasus Right-Left
if bf < -1 and self.balance_factor(node.right) > 0:
node.right = self.rotate_right(node.right)
return self.rotate_left(node)
return node
def insert(self, node, value):
# Sisipkan seperti Binary Search Tree biasa
if node is None:
return AVLNode(value)
if value < node.value:
node.left = self.insert(node.left, value)
else:
node.right = self.insert(node.right, value)
# Setelah insert, node harus dicek ulang keseimbangannya
return self.balance(node)
# Contoh penggunaan
avl = AVLTree()
root = None
for value in [1, 2, 3, 4, 5]: # Data terurut tetap bisa dijaga seimbang oleh AVL
root = avl.insert(root, value)
print(f"Root setelah insert berurutan: {root.value}")
print(f"Tinggi root: {root.height}")
# Output yang diharapkan:
# > Root setelah insert berurutan: 2
# > Tinggi root: 3Perhatikan: meski kita memasukkan 1, 2, 3, 4, 5 secara berurutan, AVL Tree tetap seimbang. Root bukan 1 melainkan 2 karena ada rotasi otomatis.
Perbandingan Head-to-Head: Kapan Menggunakan Masing-Masing?
Tabel Kompleksitas
| Operasi | BST (rata-rata) | BST (terburuk) | AVL Tree |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
| Space | O(n) | O(n) | O(n) |
AVL Tree selalu O(log n) karena ketinggian tree dijamin maksimal 1.44 × log₂(n).
Kapan Pilih BST?
Pilih BST ketika:
- Data masuk secara acak dan distribusinya merata
- Implementasi simpel lebih diprioritaskan daripada performa konsisten
- Digunakan untuk prototyping atau dataset kecil (< 10.000 elemen)
- Kamu sudah tahu pola data tidak akan membentuk urutan yang panjang
Kapan Pilih AVL Tree?
Pilih AVL Tree ketika:
- Performa pencarian yang konsisten adalah kebutuhan utama
- Data bisa datang dalam urutan terurut atau hampir terurut
- Sistem membutuhkan jaminan waktu respons (misalnya sistem real-time)
- Operasi read (search) jauh lebih sering dari write (insert/delete)
Catatan: AVL Tree lebih “mahal” di operasi insert/delete karena ada overhead rotasi. Jika frekuensi insert/delete sangat tinggi, pertimbangkan Red-Black Tree yang rotasinya lebih sedikit.
Contoh Kasus Nyata
Skenario 1: Sistem Pencarian Produk
Bayangkan kamu membangun fitur pencarian produk untuk platform e-commerce seperti Tokopedia atau Shopee. Database produk bisa mencapai jutaan item, dan nama produk sering kali dimasukkan secara berurutan (berdasarkan ID atau timestamp).
Dalam kasus ini, AVL Tree adalah pilihan yang tepat karena:
- Data produk baru terus ditambahkan (insert sering)
- Pencarian harus cepat dan konsisten untuk semua pengguna
- Tidak ada jaminan urutan data masuk
class Node:
def __init__(self, value, nama):
self.value = value # ID produk
self.nama = nama # Nama produk
self.left = None
self.right = None
self.height = 1 # Tinggi awal node baru
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
return self.get_height(node.left) - self.get_height(node.right) if node else 0
def rotate_right(self, y):
# Rotasi kanan untuk menyeimbangkan subtree
x = y.left
t2 = x.right
x.right = y
y.left = t2
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
def rotate_left(self, x):
# Rotasi kiri untuk menyeimbangkan subtree
y = x.right
t2 = y.left
y.left = x
x.right = t2
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, root, value, nama):
# 1. Insert seperti BST biasa
if not root:
return Node(value, nama)
if value < root.value:
root.left = self.insert(root.left, value, nama)
else:
root.right = self.insert(root.right, value, nama)
# 2. Update tinggi node setelah insert
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# 3. Hitung balance factor untuk cek apakah perlu rotasi
balance = self.get_balance(root)
# Kasus Left Left
if balance > 1 and value < root.left.value:
return self.rotate_right(root)
# Kasus Right Right
if balance < -1 and value > root.right.value:
return self.rotate_left(root)
# Kasus Left Right
if balance > 1 and value > root.left.value:
root.left = self.rotate_left(root.left)
return self.rotate_right(root)
# Kasus Right Left
if balance < -1 and value < root.right.value:
root.right = self.rotate_right(root.right)
return self.rotate_left(root)
return root
# Simulasi pencarian produk dengan AVL Tree
avl = AVLTree()
root = None
produk = [
(101, "Sepatu Lari"),
(102, "Kaos Polos"),
(103, "Tas Ransel"),
(104, "Jaket Denim"),
(105, "Topi Baseball"),
]
# Insert produk berdasarkan ID berurutan
# Pada BST biasa, urutan ini bisa membuat tree miring
# Pada AVL Tree, tree tetap seimbang karena ada rotasi otomatis
for id_produk, nama in produk:
root = avl.insert(root, id_produk, nama)
# Tampilkan root setelah balancing
print(f"Root node: {root.value} - {root.nama}")
print(f"Balance factor root: {avl.get_balance(root)}")
# Output yang diharapkan:
# > Root node: 102 - Kaos Polos
# > Balance factor root: -1Skenario 2: Autocomplete Sederhana
Untuk fitur autocomplete dengan data kata kunci yang sudah diketahui sebelumnya dan jarang berubah, BST bisa cukup — terutama jika data sudah diacak terlebih dahulu saat inisialisasi.
import random
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
# Jika tree masih kosong, node baru menjadi root
if self.root is None:
self.root = Node(key)
return
current = self.root
while True:
if key < current.key:
# Masuk ke subtree kiri jika key lebih kecil
if current.left is None:
current.left = Node(key)
return
current = current.left
elif key > current.key:
# Masuk ke subtree kanan jika key lebih besar
if current.right is None:
current.right = Node(key)
return
current = current.right
else:
# Abaikan jika data duplikat
return
def search(self, key):
# Cari data dengan membandingkan key secara bertahap
current = self.root
while current is not None:
if key == current.key:
return True
if key < current.key:
current = current.left
else:
current = current.right
return False
keywords = [
"android", "api", "array", "boolean", "backend",
"cache", "class", "database", "debug", "deploy"
]
# Acak urutan data sebelum insert agar tree tidak mudah menjadi miring
random.shuffle(keywords)
bst = BST()
for kw in keywords:
# Masukkan setiap keyword ke dalam Binary Search Tree
bst.insert(kw)
print("Cari 'cache':", bst.search("cache"))
print("Cari 'frontend':", bst.search("frontend"))
# Output yang diharapkan:
# > Cari 'cache': True
# > Cari 'frontend': FalsePerbandingan Performa Langsung
Ini juga berkaitan dengan pemilihan algoritma yang tepat — topik yang dibahas di Membandingkan Algoritma Sorting: Kapan Menggunakan Bubble, Merge, dan Quick Sort?. Prinsipnya sama: pilih struktur data atau algoritma berdasarkan karakteristik data dan pola operasi, bukan hanya popularitas.
import time
import random
class BSTNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
# Jika root kosong, node pertama menjadi root
if self.root is None:
self.root = BSTNode(value)
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = BSTNode(value)
return
current = current.left
else:
if current.right is None:
current.right = BSTNode(value)
return
current = current.right
def search(self, value):
# Cari nilai dengan menelusuri pohon dari root
current = self.root
while current is not None:
if value == current.value:
return True
current = current.left if value < current.value else current.right
return False
class AVLNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def _height(self, node):
return 0 if node is None else node.height
def _update_height(self, node):
node.height = 1 + max(self._height(node.left), self._height(node.right))
def _balance_factor(self, node):
return self._height(node.left) - self._height(node.right)
def _rotate_right(self, y):
x = y.left
t2 = x.right
x.right = y
y.left = t2
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
y = x.right
t2 = y.left
y.left = x
x.right = t2
self._update_height(x)
self._update_height(y)
return y
def _insert(self, node, value):
# Sisipkan node seperti BST biasa
if node is None:
return AVLNode(value)
if value < node.value:
node.left = self._insert(node.left, value)
else:
node.right = self._insert(node.right, value)
# Perbarui tinggi lalu cek keseimbangan
self._update_height(node)
balance = self._balance_factor(node)
# Rotasi jika pohon tidak seimbang
if balance > 1 and value < node.left.value:
return self._rotate_right(node)
if balance < -1 and value > node.right.value:
return self._rotate_left(node)
if balance > 1 and value > node.left.value:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance < -1 and value < node.right.value:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def insert(self, value):
self.root = self._insert(self.root, value)
def search(self, value):
# Pencarian tetap mirip BST
current = self.root
while current is not None:
if value == current.value:
return True
current = current.left if value < current.value else current.right
return False
def benchmark(tree_class, data):
# Ukur waktu insert dan search
tree = tree_class()
start = time.perf_counter()
for value in data:
tree.insert(value)
for value in data[:100]:
tree.search(value)
return time.perf_counter() - start
# Data terurut: kasus buruk untuk BST biasa
sorted_data = list(range(1000))
# Data acak: biasanya membuat BST lebih seimbang
random_data = random.sample(range(10000), 1000)
bst_sorted = benchmark(BST, sorted_data)
bst_random = benchmark(BST, random_data)
avl_sorted = benchmark(AVLTree, sorted_data)
avl_random = benchmark(AVLTree, random_data)
print(f"BST + data terurut : {bst_sorted:.6f} detik")
print(f"BST + data acak : {bst_random:.6f} detik")
print(f"AVL + data terurut : {avl_sorted:.6f} detik")
print(f"AVL + data acak : {avl_random:.6f} detik")
# Output yang diharapkan:
# > BST + data terurut : [angka waktu] detik
# > BST + data acak : [angka waktu] detik
# > AVL + data terurut : [angka waktu] detik
# > AVL + data acak : [angka waktu] detikPertanyaan yang Sering Diajukan
Apa itu balance factor dalam AVL Tree?
Balance factor adalah selisih antara tinggi subtree kiri dan subtree kanan dari sebuah node. Nilai yang valid dalam AVL Tree adalah -1, 0, atau +1. Jika balance factor melebihi rentang ini setelah operasi insert atau delete, tree melakukan rotasi otomatis untuk menyeimbangkan diri.
Mengapa BST bisa menjadi lambat seperti linked list?
BST menjadi lambat ketika data dimasukkan dalam urutan yang sudah terurut (ascending atau descending). Hasilnya adalah skewed tree di mana semua node hanya memiliki anak di satu sisi. Ini membuat tinggi tree menjadi n (jumlah node), sehingga operasi yang seharusnya O(log n) menjadi O(n).
Apa perbedaan AVL Tree dengan Red-Black Tree?
Keduanya adalah self-balancing BST, namun berbeda pendekatan. AVL Tree lebih ketat dalam menjaga keseimbangan (balance factor maksimal ±1), sehingga pencarian lebih cepat. Red-Black Tree lebih longgar namun memerlukan lebih sedikit rotasi saat insert/delete, membuatnya lebih efisien untuk operasi tulis yang sering. Banyak implementasi std::map di C++ menggunakan Red-Black Tree karena alasan ini.
Bagaimana cara menentukan pilihan antara BST dan AVL Tree di proyek nyata?
Tanyakan dua hal: (1) Seberapa sering operasi insert/delete terjadi? (2) Apakah kamu bisa menjamin data masuk secara acak? Jika insert/delete jarang dan data acak, BST sudah cukup. Jika data bisa terurut atau performa pencarian harus konsisten, gunakan AVL Tree. Untuk kasus umum di production, banyak developer langsung menggunakan implementasi yang sudah ada seperti SortedList di Python atau TreeMap di Java yang berbasis Red-Black Tree.
Apakah library Python menyediakan implementasi AVL Tree bawaan?
Python tidak menyediakan AVL Tree secara built-in, namun modul sortedcontainers (install via pip install sortedcontainers) menyediakan SortedList, SortedDict, dan SortedSet yang efisien. Untuk kebutuhan production, sangat disarankan menggunakan library tersebut daripada mengimplementasikan AVL Tree dari nol.
Kesimpulan
BST dan AVL Tree keduanya berguna, namun untuk tujuan yang berbeda:
- BST cocok untuk implementasi cepat dengan data acak dan kebutuhan sederhana. Mudah dipahami dan diimplementasikan, tapi rentan terhadap skewed tree.
- AVL Tree adalah pilihan lebih aman untuk production karena menjamin performa
O(log n)di semua kasus, dengan biaya overhead rotasi yang kecil saat insert/delete.
Dalam praktik sehari-hari, jarang sekali developer mengimplementasikan kedua struktur data ini dari nol. Yang lebih penting adalah memahami konsep keseimbangan ini agar kamu bisa membuat keputusan tepat saat memilih struktur data bawaan bahasa pemrograman, seperti menggunakan dict vs SortedDict di Python atau HashMap vs TreeMap di Java.
Pemahaman ini juga akan membantumu saat merancang arsitektur sistem yang lebih kompleks — prinsip yang sama berlaku di banyak design pattern yang membutuhkan struktur data efisien sebagai fondasinya, seperti yang dibahas di Mengenal Design Patterns: Fondasi Arsitektur Plugin yang Scalable.