Binary Tree & Binary Search Tree

Tree adalah struktur hierarkis: satu root, dan setiap node punya nol atau lebih anak. Pada binary tree, setiap node punya paling banyak dua anak: kiri dan kanan.

Istilah

• Leaf (daun): node tanpa anak.
• Depth/level sebuah node: jumlah sisi dari root ke node itu (root = 0).
• Height tree: depth terbesar (+1 jika menghitung node; di catatan ini height = banyaknya level).
• Subtree: sebuah node beserta semua keturunannya. Setiap subtree juga sebuah tree, sehingga hampir semua algoritma tree bersifat rekursif.
• Full binary tree: setiap node punya 0 atau 2 anak. Complete: semua level penuh kecuali mungkin level terakhir yang terisi dari kiri (bentuk dasar heap).

Binary Search Tree (BST)

BST adalah binary tree dengan aturan: untuk setiap node, semua nilai di subtree kiri lebih kecil, dan semua nilai di subtree kanan lebih besar. Akibatnya, pencarian cukup mengikuti satu jalur dari root, seperti binary search.

Binary Search Tree

insertsearchdeleteinorderpreorderpostorderlevelorderKosongkan

Klik operasi di bawah, atau klik sebuah node untuk menghapusnya.

n = 8 · tinggi h = 4 · tinggi minimum ⌈log₂(n+1)⌉ = 4. Coba insert angka terurut (1, 2, 3, …) dan lihat tree jadi “linked list”.

Coba ini di widget:

1. search 35: perhatikan jalurnya 50 → 30 → 40 → 35, hanya 4 perbandingan.
2. inorder: hasilnya selalu terurut. Inilah cara “mengurutkan” pakai BST.
3. Kosongkan, lalu insert 10, 20, 30, 40, 50 berurutan. Tree menjadi miring dan tingginya $n$, sehingga search jatuh ke $O(n)$. Inilah alasan adanya balanced BST (AVL, Red-Black tree).
4. delete 30 (punya dua anak): nilainya diganti in-order successor (nilai terkecil di subtree kanan).

Traversal

Nama	Urutan	Contoh dipakai untuk
Preorder	node, kiri, kanan	menyalin tree, ekspresi prefix
Inorder	kiri, node, kanan	BST → urutan terurut
Postorder	kiri, kanan, node	menghapus tree, ekspresi postfix
Level order	per level (pakai queue)	BFS, mencetak per tingkat

Traversal rekursif + tinggi tree▶ Jalankan

Kompleksitas BST

Operasi	Rata-rata (seimbang)	Terburuk (miring)
search / insert / delete	$O(\log n)$	$O(n)$
traversal	$O(n)$	$O(n)$

Cek pemahaman

1. 1. Hasil inorder dari BST selalu…

   A.AcakB.Terurut menaikC.Terurut menurunD.Sama dengan preorder

2. 2. Data 1..7 di-insert berurutan ke BST kosong. Tingginya?

   A.3B.4C.7D.1

3. 3. Saat menghapus node dengan dua anak, nilainya biasanya diganti dengan…

   A.RootB.Anak kiriC.In-order successor atau predecessorD.Daun mana saja

Latihan: Kedalaman Maksimum Tree, Invert Binary Tree, Validasi BST.