Bab 7
Pohon (Tree)
Graf paling hemat sengaja: tidak ada satu sisi pun yang mubazir, namun semua simpul tetap saling terhubung. Bab ini membedahnya dari nol — definisi, sifat, pohon merentang, pohon biner, hingga kode Huffman — dengan mesin-mesin interaktif yang bisa Anda jalankan sendiri.
Semua yang bergaris tepi tebal adalah mesin: klik, geser, jalankan.
Apa Itu Pohon?
Bayangkan Anda harus menghubungkan semua gedung kampus dengan kabel, semua orang dalam satu silsilah keluarga, atau semua folder dalam satu direktori. Ketiganya punya pola sama: semua tersambung, tetapi tidak ada jalur yang mengembali ke tempat semula. Pola itulah pohon.
Pohon = graf terhubung tanpa siklus
Sebuah graf tak berarah $G=(V,E)$ disebut pohon jika dan hanya jika $G$ terhubung (dari simpul mana pun kita bisa sampai ke simpul mana pun) dan tidak memuat satu siklus pun.
$\qquad\quad\iff$ (ii) $G$ tak bersiklus dan $|E| = |V|-1$
$\qquad\quad\iff$ (iii) setiap dua simpul dihubungkan tepat satu lintasan sederhana
Tiga tanda ini ekuivalen: penuhi satu, Anda otomatis memenuhi dua lainnya. Sifat (iii) adalah cara paling elegan — nol redundansi.
Kedua cek itu sudah cukup — jika sisi tepat $n-1$ dan terhubung, siklus mustahil ada (siklus butuh sisi "tambahan").
Diawali dengan satu siklus besar. Matikan / nyalakan sisi sampai status menjadi pohon sah.
Sisi berlebih = 1. Siklus lahir ketika sisi "lebih" dari pohon yang terhubung.
→ pohon adalah kasus khusus $c=1$: $|E| = |V|-1$
Nama-nama Bagian Pohon
Karena pohon biasanya digambar "menggantung" dari satu titik atas (akar), lahirlah istilah kekeluargaan: orang tua, anak, saudara, daun. Arahkan kursor ke setiap simpul pada diagram di bawah — panel kanan akan menjelaskan perannya.
Pohon contoh $T$ — akarnya $A$, tinggi 2.
Arahkan kursor (atau ketuk) salah satu simpul untuk melihat istilahnya.
| Istilah | Arti |
|---|---|
| akar (root) | Simpul tertinggi; satu-satunya tanpa orang tua. |
| daun (leaf) | Simpul tanpa anak; ujung cabang. |
| parent / child | Simpul tepat di atas / tepat di bawah suatu sisi. |
| sibling | Anak-anak dari orang tua yang sama. |
| tingkat (depth) | Jarak dari akar; akar berada di tingkat $0$. |
| tinggi (height) | Tingkat maksimum di seluruh pohon. |
| derajat | Banyak sisi yang menempel pada simpul. |
| hutan | Kumpulan pohon terpisah (graf tak bersiklus apa pun). |
Sepanjang §7.1–§7.2 kita memakai satu kasus yang sama: kampus dengan 7 gedung yang akan dijaring dengan kabel fiber — A Rektorat · B Lab Terpadu · C Perpustakaan · D Asrama · E Kantin · F Auditorium · G Stadion. Kabel antar gedung punya biaya (bobot) berbeda. Pertanyaan besarnya: pasang kabel di mana agar semua tersambung dengan total biaya minimum? Jawabannya: bangun sebuah pohon merentang minimum — dan tepat 6 kabel (ingat $n-1$!).
Mengapa Selalu $n-1$ Sisi?
Setiap pohon dengan $n \ge 1$ simpul memiliki tepat $n-1$ sisi.
Untuk $n>1$: pohon selalu punya $\ge 2$ daun (ujung lintasan terpanjang).
Lepas daun $u$ beserta sisi $uv$ → pohon $n-1$ simpul, sisi $(n-1)-1$.
Kembalikan $u$: $|E| = (n-2)+1 = n-1$. $\blacksquare$
Dari mana asalnya? Karena tak ada siklus, setiap sisi wajib "mengenalkan" satu simpul baru — sehingga jumlahnya persis selisih simpul terhadap satu.
− 1 sisi dari pohon $\Rightarrow$ putus jadi 2 komponen
Pohon berada di tepi pisau: paling longgar yang masih terhubung, paling ketat yang masih bebas siklus. Inilah alasan algoritma MST berhati-hati memeriksa siklus.
Uji Pemahaman — benar atau salah?
Setiap pohon dengan $n$ simpul memiliki tepat $n-1$ sisi.
Menambah satu sisi ke pohon selalu menciptakan tepat satu siklus baru.
Sebuah pohon boleh memiliki simpul terisolasi (tanpa sisi menempel).
Setiap graf tak berarah yang tak bersiklus pastilah pohon.
Menghapus satu sisi apa pun dari pohon memutusnya menjadi tepat dua komponen.
Jaringan kampus punya $n=7$ gedung. Berapa kabel pada pohon merentangnya? $7-1=\mathbf{6}$ kabel — tidak lebih, tidak kurang.
Merentang Semua, Buang yang Mahal
Diberi graf terhubung berbobot (misal: biaya kabel antar gedung). Pohon merentang adalah subgraf yang (1) memuat semua simpul, (2) berbentuk pohon — terhubung dan hanya $n-1$ sisi. Jika total bobotnya minimum, ia disebut MST (Minimum Spanning Tree).
Belah simpul graf jadi dua kelompok $S$ dan $V\setminus S$. Sisi termurah yang melintasi belahan itu pasti aman diambil ke MST.
Dari mana asalnya? Misal MST $T$ tidak memuat $e$. Tambahkan $e$ → lahir satu siklus, dan siklus itu harus menyeberangi potongan sekali lagi lewat sisi $e'$. Tukar $e'$ dengan $e$: pohon tetap sah, total bobot turun atau tetap. Kontradiksi dengan kemahalan $e$ — berarti $e$ memang layak masuk.
$\xrightarrow{\ \text{tambah } c-1 \text{ sisi tepat}\ }$ satu pohon utuh
Tiap sisi penghubung menggabungkan dua komponen menjadi satu, jadi jumlah komponen berkurang tepat satu per sisi.
Kruskal: Urutkan, lalu Waspadai Siklus
Ide Kruskal (1956) sederhana namun cerdas: urutkan semua sisi dari termurah, lalu ambil satu per satu — asalkan tidak membentuk siklus. Pemeriksa siklusnya memakai struktur Union-Find: dua simpul yang sudah satu "keluarga" tak boleh dihubungkan lagi.
A Rektorat B Lab C Perpus D Asrama E Kantin F Auditorium G Stadion
T ← ∅ ; setiap simpul jadi kelompok sendiri
untuk setiap e = (u,v) di E terurut:
jika find(u) ≠ find(v):
T ← T ∪ {e} ; union(u,v)
jika |T| = n−1: berhenti
Union-Find hampir $O(1)$ per operasi (path compression)
Cocok saat graf jarang sisi ($E$ kecil) dan sisi sudah tersaji sebagai daftar — persis seperti daftar penawaran kabel di layar mesin di atas.
Prim: Tumbuh dari Satu Gedung
Prim menanam pohon dari satu simpul (kita mulai dari A Rektorat) dan berulang kali menarik sisi termurah yang menjulur keluar dari wilayah yang sudah tersambung — persis mengikuti cut property dengan $S$ = wilayah tersambung.
Kruskal maupun Prim wajib berakhir di total yang sama: 28. Struktur pilihannya bisa berbeda urutan, tetapi biaya minimum itu unik (bobot sisi kita sengaja dibuat semua berbeda).
Kruskal vs Prim — kapan memakai yang mana?
| Aspek | Kruskal | Prim |
|---|---|---|
| strategi | Global: seleksi seluruh sisi termurah | Lokal: kembangkan satu pohon |
| struktur data kunci | sort + Union-Find | priority queue / heap |
| kompleksitas | $O(E\log E)$ | $O(E\log V)$ (heap biner) |
| unggul saat | graf jarang, sisi sudah berdaftar | graf padat, tetangga mudah diakses |
| graf tak terhubung? | menghasilkan hutan merentang | hanya merentang satu komponen |
Pohon yang Disiplin: Maksimal Dua Anak
Pohon biner adalah pohon berakar di mana setiap simpul punya paling banyak dua anak: anak kiri dan anak kanan. Definisinya pun rekursif — paling pas, karena seluruh teorinya tumbuh secara rekursif.
(i) hampa, atau
(ii) sebuah simpul akar + pohon biner kiri + pohon biner kanan
Dari definisi ini lahir tiga traversal §7.3b dan rumus-rumus penghitungan simpul — semuanya "diperas" dari struktur (ii).
minimum simpul: $n_{\min} = h+1$ (pohon miring)
$\Rightarrow\ \lceil\log_2(n+1)\rceil - 1 \le h \le n-1$
Sisi halus (logaritmik) vs sisi kasar (linier) — perbedaan inilah yang menggerakkan seluruh ilmu pencarian (BST, AVL, heap).
Titik oker = daun ($2^h$ buah); tiap tambahan tinggi menggandakan daun — itu $2^{h+1}-1$ bekerja.
Empat wajah pohon biner
Setiap simpul beranak 0 atau 2 — tak ada anak tunggal.
Terisi rapat kiri→kanan per tingkat; dasar struktur heap.
Semua daun sedalam mungkin; $n = 2^{h+1}-1$.
Menyamping total — pohon biner menyamar jadi rantai.
Tiga Cara Menyusuri: Kapan Akar Dikunjungi?
Traversal = aturan membaca seluruh simpul tepat satu kali. Seluruh rahasianya satu kalimat: kapan akar dikunjungi relatif terhadap subtree kiri (L) dan kanan (R). Kiri selalu didahulukan sebelum kanan; yang bergeser hanyalah posisi akar (A):
preorder(kiri)
preorder(kanan)
Akar di awal → untuk menyalin pohon & ekspresi prefiks.
kunjungi akar
inorder(kanan)
Akar di tengah → pada BST menghasilkan urutan terurut naik.
postorder(kanan)
kunjungi akar
Akar di akhir → untuk menghapus pohon & ekspresi postfix.
Oker berdenyut = sedang dikunjungi; teal = selesai dicatat.
Pohon biner juga menyimpan ekspresi matematika: operator jadi akar/internal, operand jadi daun. Bandingkan hasil bacanya:
preorder → * + a b c (notasi prefiks) · inorder → a + b * c (perlu tanda kurung) · postorder → a b + c * (notasi postfix — tanpa kurang kurung sama sekali!)
BST: Pohon yang Bisa Dicari
Aturan BST hanya satu: untuk setiap simpul, seluruh subtree kiri bernilai lebih kecil, subtree kanan lebih besar. Konsekuensinya menakjubkan — inorder traversal otomatis mengeluarkan angka terurut, dan pencarian tinggal "belok kiri atau kanan" tiap tingkat.
Dengan induksi: inorder pada BST menghasilkan subtree kiri (semua kecil), lalu akar, lalu subtree kanan (semua besar). Rangkaian "kecil → akar → besar" plus sifat rekursif = urutan naik untuk seluruh pohon. $\blacksquare$
$h$ terbaik $\approx \log_2 n$, terburuk $= n-1$ (pohon miring)
Pohon yang Mengambil Keputusan
Di dunia nyata, pohon juga berperan sebagai mesin penanya jawaban: simpul internal menyimpan pertanyaan, cabang menyimpan jawaban, dan daun menyimpan keputusan akhir. Setiap data hanya menempuh satu jalur akar→daun — panjang jalur itulah "biaya" keputusannya.
Dari ukuran ketidakpastian — entropi. Pertanyaan terbaik adalah yang paling besar membelah ketidakpastian data:
$\text{Gain}(A) = H(S) - \sum_{v} \tfrac{|S_v|}{|S|}\,H(S_v)$
Atribut dengan Gain terbesar duduk di akar; ulangi secara rekursif per cabang (algoritma ID3/C4.5). Pohon keputusan = greedy yang rapi.
Memadatkan Teks tanpa Kehilangan Makna
Komputer menyimpan huruf sebagai bit. Memberi setiap huruf panjang yang sama itu mudah tetapi boros. Memberi panjang bebas itu hemat tetapi berbahaya: bagaimana memecah bit kembali menjadi huruf?
Taruh huruf hanya di daun; bangun kode dengan berjalan dari akar: belok kiri catat 0, belok kanan catat 1. Karena daun tak punya kelanjutan, tidak ada kode yang menjadi awalan kode lain — otomatis prefiks-free.
total bit: $\;\sum_i f_i \cdot d_i$ ($f_i$ = frekuensi, $d_i$ = kedalaman)
Itulah algoritma Huffman (1952) — dan bagian menyenangkannya: pohon Huffman yang dihasilkan terbukti optimal, tak ada kode prefiks lain yang lebih hemat untuk distribusi frekuensi yang sama. Waktunya membuktikannya dengan mesin.
Mesin 08 · Pabrik Kode Huffman
Ketik teks apa pun (pegangan default: HUFFMAN), lalu Bangun Pohon. Perhatikan: dua kotak termurah berdenyut oker, melebur jadi satu orang tua, dan begitu seterusnya sampai tersisa satu akar.
$H = -\sum_i p_i \log_2 p_i$ (entropi sumber)
Tidak ada kode prefiks yang bisa mengalahkan Huffman untuk frekuensi yang diberikan — hasil penuh pertukaran-pertukaran cut property gaya Huffman: dua simbol terlangka selalu jadi bersaudara paling dalam.
Kartu Hafalan Bab 7
Delapan lembar sari pati — kalau hanya satu halaman yang bisa Anda bawa ujian, bawalah yang ini.
+1 sisi → tepat 1 siklus; −1 sisi → putus 2 komponen.
Kruskal $O(E\log E)$ · Prim $O(E\log V)$ — hasil biaya minimum selalu sama.
Sempurna: $n = 2^{h+1}-1$, daun $=2^h$. Full binary: daun $=$ internal $+1$.
Inorder BST = urutan naik. Banyak bentuk pohon biner dengan $n$ simpul $=\frac{1}{n+1}\binom{2n}{n}$ (Catalan).
Atribut ber-Gain terbesar duduk di akar; daun = keputusan.
Dua terkecil digabung, ulangi sampai satu akar; kiri = 0, kanan = 1.