Tree
Pengantar Struktur Data Tree
Struktur data tree adalah salah satu konsep dasar dalam ilmu komputer yang sering muncul dalam wawancara software engineer, terutama untuk memahami hierarki data dan operasi efisien. Tree mirip dengan pohon di dunia nyata, dengan akar (root) di atas dan cabang-cabang yang mewakili hubungan parent-child. Ini berguna untuk mewakili data berhierarki seperti sistem file, organisasi perusahaan, atau parsing ekspresi matematika. Berikut poin kunci utama:
Definisi Dasar: Tree terdiri dari node yang terhubung via edge, tanpa siklus. Setiap node bisa punya anak (child) dan satu orang tua (parent), kecuali root.
Varian Umum: Mulai dari Binary Tree sederhana hingga self-balancing seperti AVL atau Red-Black untuk efisiensi. Varian lain seperti Trie untuk string dan Segment Tree untuk query range.
Keuntungan: Efisien untuk pencarian dan penyisipan dibanding array atau linked list, terutama jika seimbang (O(log n) vs O(n)).
Potensi Masalah: Jika tidak seimbang, performa bisa menurun ke O(n), sehingga varian self-balancing direkomendasikan.
Mengapa Tree Penting untuk Interview?
Pengetahuan tree menunjukkan pemahaman tentang rekursi dan efisiensi algoritma. Wawancara sering meminta implementasi traversal atau balancing. Untuk detail lebih lanjut, lihat sumber seperti GeeksforGeeks Binary Tree atau Wikipedia Tree.
Tips Persiapan
Latih kode di Go untuk traversal dan operasi dasar. Pahami trade-off: Binary Tree sederhana tapi bisa tidak efisien; AVL ketat dalam balancing tapi lebih kompleks daripada Red-Black.
Struktur data tree adalah fondasi penting dalam ilmu komputer, sering digunakan untuk mewakili hubungan hierarkis dan mendukung operasi efisien seperti pencarian, penyisipan, dan penghapusan. Dalam konteks wawancara software engineer, pemahaman mendalam tentang tree dan variannya—seperti Binary Tree, Binary Search Tree (BST), AVL Tree, Red-Black Tree, B-Tree, Trie, dan Segment Tree—sangat krusial karena topik ini muncul dalam sekitar 20-30% pertanyaan algoritma, terutama yang melibatkan rekursi, balancing, dan optimasi waktu/ruang. Penjelasan ini mencakup intuisi, mekanisme kerja, operasi utama, analisis Big O (dengan derivasi matematis), dan implementasi kode dalam Go, berdasarkan prinsip standar ilmu komputer. Semua kompleksitas diasumsikan untuk kasus rata-rata pada tree seimbang, dengan catatan worst-case jika relevan.
Dasar-Dasar Tree
Intuisi: Bayangkan tree seperti pohon keluarga—root adalah leluhur tertinggi, dan cabang mewakili keturunan. Ini non-linear, berbeda dari array atau list, sehingga cocok untuk data berhierarki tanpa siklus. Penjelasan: Tree terdiri dari node (data + pointer ke child), edge (hubungan), root (titik mulai), leaf (node tanpa child), depth (jarak dari root), dan height (jarak terpanjang ke leaf). Degree adalah jumlah child maksimal; untuk binary, degree=2. Operasi Umum: Traversal (kunjungi node), insert, delete, search. Big O: Bergantung varian; traversal O(n), operasi lain O(height). Derivasi: Height h=log n untuk seimbang, jadi ops O(log n); worst (skewed) h=n, O(n). Kode Go Dasar (Node Struktur):
type Node struct {
Val int
Left *Node
Right *Node // Untuk binary; extend untuk varian lain
}Ini basis untuk semua varian.
Varian Tree: Penjelasan Komprehensif
Berikut tabel ringkasan varian tree umum, berdasarkan analisis standar:
Binary Tree
Pohon sederhana dengan maks 2 child, seperti cabang biner.
Setiap node punya <=2 child (left/right); bisa full (0/2 child), complete (level penuh kecuali terakhir), perfect (semua level penuh).
Traversal, insert, delete.
Traversal O(n); ops O(h) (h=log n seimbang, n skewed). Derivasi: Rekursi tingkat log n.
Ekspresi matematika, heap.
Binary Search Tree (BST)
Dictionary terurut, seperti pencarian biner tapi dinamis.
Left < parent < right; subtrees juga BST.
Search, insert, delete.
O(log n)/O(n); derivasi T(n)=T(n/2)+O(1) → log n.
Database indexing, sorting.
AVL Tree
BST dengan auto-balance, seperti timbangan yang selalu seimbang.
Self-balancing BST; balance factor ≤1, pakai rotations (LL, RR, LR, RL).
Search, insert+rotate, delete+rotate.
O(log n) semua; rotations O(1), total log n.
Real-time apps, balanced search.
Red-Black Tree
BST balanced dengan warna, seperti aturan permainan untuk keseimbangan.
Self-balancing BST; node red/black, aturan: no adjacent red, black path sama.
Search, insert+recolor/rotate.
O(log n); mirip AVL tapi rotasi lebih sedikit.
Java TreeMap, file systems.
B-Tree
Tree multi-way untuk disk, seperti indeks buku tebal.
Node punya multiple key/child (order m); balanced, leaf sama level.
Search, insert, delete.
O(log n); branching factor tinggi kurangi height.
Database (MySQL), file systems.
Trie (Prefix Tree)
Pohon untuk string, seperti kamus dengan prefix.
Node wakili char; child variabel (misal 26 untuk alfabet).
Insert, search, prefix search.
O(m) (m=panjang string); tak bergantung n.
Autocomplete, spell checker.
Segment Tree
Tree untuk range query, seperti indeks segmen array.
Node wakili interval array; root seluruh array.
Build, query (range), update.
Build O(n), query/update O(log n).
Range sum/min/max, image processing.
Binary Tree Intuisi: Struktur sederhana untuk hierarki, tanpa aturan urut. Mekanisme: Node dengan left/right; bisa skewed (linked list) atau balanced. Traversal: Depth-first (pre/in/post-order) atau breadth-first (level order). Derivasi Big O: Kunjungi n node, O(n). Kode Go (Traversal):
func inorder(root *Node) { // Left-Root-Right
if root == nil { return }
inorder(root.Left)
fmt.Print(root.Val, " ")
inorder(root.Right)
}
func preorder(root *Node) { // Root-Left-Right
if root == nil { return }
fmt.Print(root.Val, " ")
preorder(root.Left)
preorder(root.Right)
}
func postorder(root *Node) { // Left-Right-Root
if root == nil { return }
postorder(root.Left)
postorder(root.Right)
fmt.Print(root.Val, " ")
}
import "container/list"
func levelOrder(root *Node) { // BFS
if root == nil { return }
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0 {
elem := queue.Remove(queue.Front()).(*Node)
fmt.Print(elem.Val, " ")
if elem.Left != nil { queue.PushBack(elem.Left) }
if elem.Right != nil { queue.PushBack(elem.Right) }
}
}Penggunaan: Bangun tree, panggil inorder(root) untuk urut terurut jika BST.
Binary Search Tree (BST) Intuisi: Tree terurut untuk pencarian cepat, seperti buku telepon biner. Mekanisme: Insert: rekursi left jika <, right jika >. Search/delete mirip. Delete: Handle leaf, one child, two child (ganti dengan inorder successor). Big O: O(log n) rata-rata; worst O(n) jika skewed. Derivasi: Divide-and-conquer, T(n)=T(n/2)+O(1) → log n (Master Theorem). Kode Go:
func insert(root *Node, val int) *Node {
if root == nil { return &Node{Val: val} }
if val < root.Val { root.Left = insert(root.Left, val) }
else if val > root.Val { root.Right = insert(root.Right, val) }
return root
}
func search(root *Node, val int) bool {
if root == nil { return false }
if root.Val == val { return true }
if val < root.Val { return search(root.Left, val) }
return search(root.Right, val)
}
func deleteNode(root *Node, val int) *Node {
if root == nil { return nil }
if val < root.Val { root.Left = deleteNode(root.Left, val) }
else if val > root.Val { root.Right = deleteNode(root.Right, val) }
else {
if root.Left == nil { return root.Right }
if root.Right == nil { return root.Left }
minVal := minValue(root.Right)
root.Val = minVal
root.Right = deleteNode(root.Right, minVal)
}
return root
}
func minValue(node *Node) int {
min := node.Val
for node.Left != nil {
min = node.Left.Val
node = node.Left
}
return min
}Penggunaan: root := insert(nil, 50); search(root, 50) → true.
AVL Tree Intuisi: BST yang selalu seimbang untuk menghindari kemiringan, menggunakan rotasi seperti penyeimbang otomatis. Mekanisme: Hitung balance factor (height left - right); jika >1 atau <-1, lakukan rotasi (LL, RR, LR, RL). Insert/delete seperti BST, lalu rebalance. Big O: O(log n) semua kasus; rotasi O(1), total log n. Derivasi: Height selalu log n karena balancing. Kode Go (Sederhana, tanpa full rotations untuk breviti; extend dari BST): Tambah height dan balance ke Node; implement rotasi. Untuk lengkap, lihat GeeksforGeeks AVL Insertion.
Red-Black Tree Intuisi: BST balanced dengan "warna" untuk fleksibilitas, kurang ketat daripada AVL tapi efisien. Mekanisme: Node red/black; aturan: root black, no two red adjacent, same black nodes per path. Rebalance via recolor/rotate. Big O: O(log n); mirip AVL. Kode Go: Kompleks; gunakan std lib jika avail, atau implement manual (lihat sources).
B-Tree Intuisi: Tree lebar untuk data besar, minimisasi disk access. Mekanisme: Node multi-key/child; insert/search seperti BST tapi split jika full. Varian B+: Data di leaf. Big O: O(log n); height kecil karena branching tinggi. Kode Go: Gunakan array untuk child/keys per node.
Trie Intuisi: Tree untuk string, efisien prefix match. Mekanisme: Node punya array child (e.g., 26 untuk alfabet); insert: buat path per char, mark endOfWord. Search: ikuti path, cek end. Big O: O(m) untuk ops, m=string length. Derivasi: Linear scan per char. Kode Go:
type TrieNode struct {
Children [26]*TrieNode
IsEnd bool
}
func insert(root *TrieNode, key string) {
curr := root
for _, c := range key {
idx := c - 'a'
if curr.Children[idx] == nil { curr.Children[idx] = &TrieNode{} }
curr = curr.Children[idx]
}
curr.IsEnd = true
}
func search(root *TrieNode, key string) bool {
curr := root
for _, c := range key {
idx := c - 'a'
if curr.Children[idx] == nil { return false }
curr = curr.Children[idx]
}
return curr.IsEnd
}Penggunaan: root := &TrieNode{}; insert(root, "hello"); search(root, "hello") → true.
Segment Tree Intuisi: Tree untuk query range efisien, seperti indeks segmen data. Mekanisme: Build: Rekursi bagi array jadi segmen, store sum/min/etc di node. Query: Gabung segmen relevan. Update: Ubah leaf, propagate up. Big O: Build O(n), query/update O(log n). Derivasi: Height log n, tiap level O(1). Kode Go: Kompleks; gunakan array untuk tree (index 1=root). Untuk lengkap, lihat GeeksforGeeks.
Ini mencakup esensi tree untuk persiapan interview; latih variasi seperti handling duplikat atau lazy propagation di segment tree.
Key Citations
Last updated