Matdis — Bab 10

Pohon (Trees)

Struktur graf khusus tanpa siklus — tulang punggung struktur data, parsing kompiler, kompresi data, dan pohon hash untuk verifikasi integritas.

Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 10. — Rosen, Discrete Mathematics, 8th ed., Ch. 11. — CLRS, Introduction to Algorithms, 4th ed., Ch. 12, 21.

Mengapa Pohon Penting?

Hampir semua sistem komputer yang efisien menggunakan pohon: sistem file (direktori), basis data (B-tree index PostgreSQL/MySQL), parser kompiler (AST), kompresi (Huffman), jaringan (spanning tree protocol), sistem kendali versi (pohon Merkle pada Git), dan grafika (quadtree/octree untuk pencarian spasial).

Pohon adalah graf terhubung dan tanpa sirkuit — properti minimal yang menjamin satu jalur unik antara dua simpul, sifat yang membuat banyak algoritma menjadi sangat efisien (O(log n) dalam pohon seimbang).

1. Definisi dan Sifat Fundamental

Definisi (Pohon)

Pohon T = (V, E) adalah graf tak-berarah, terhubung, dan tidak mengandung sirkuit (asiklik).

Hutan (forest): graf asiklik (boleh tidak terhubung) — kumpulan pohon-pohon disjoint.

Pohon berakar (rooted tree): pohon dengan satu simpul khusus disebut akar (root).

Daun (leaf): simpul berderajat 1 (pada pohon berakar: simpul tanpa anak).

Tinggi (height): panjang lintasan terpanjang dari akar ke daun.

Kedalaman (depth): panjang lintasan dari akar ke simpul tersebut.

Teorema (Sifat Setara)

Untuk graf G dengan n simpul, pernyataan berikut ekuivalen:

G adalah pohon (terhubung dan asiklik).
G terhubung dan memiliki tepat n − 1 sisi.
G asiklik dan memiliki tepat n − 1 sisi.
Setiap pasang simpul dihubungkan oleh tepat satu lintasan.
G terhubung; menghapus sisi manapun memutus G (setiap sisi adalah bridge).
G asiklik; menambah sisi manapun menghasilkan tepat satu sirkuit.

Visualisasi: Pohon Berakar dengan Terminologi

Pohon 7 simpul, 6 sisi (=n-1). Akar=1, internal={2,3}, daun={4,5,6,7}, tinggi h=2.

2. Pohon Biner

Definisi (Pohon Biner)

Pohon berakar di mana setiap simpul memiliki paling banyak dua anak (anak kiri dan anak kanan yang dibedakan posisinya).

Pohon biner penuh (full binary tree): setiap simpul internal memiliki tepat 2 anak.

Pohon biner lengkap (complete binary tree): semua level terisi penuh kecuali (mungkin) level terakhir, terisi dari kiri.

Pohon biner seimbang (balanced): selisih tinggi subtree kiri dan kanan paling banyak 1 (AVL, Red-Black tree).

BST (Binary Search Tree): untuk setiap simpul x: nilai subtree kiri < x < nilai subtree kanan.

Teorema: Tinggi Pohon Biner

Pohon biner lengkap dengan n simpul: h = ⌊log₂ n⌋

Pohon biner penuh dengan h level: 2^(h+1) - 1 simpul

Operasi BST seimbang: O(log n) — insert, delete, search

AVL/Red-Black tree: menjamin h = O(log n) selalu

3. Traversal Pohon Biner

Eksplorasi Interaktif: Empat Strategi Kunjungan

Hasil: [ 4, 2, 5, 1, 6, 3, 7 ]

Kiri → Root → Kanan. Pada BST menghasilkan elemen terurut secara ascending.

Highlight kuning bergerak mengikuti urutan kunjungan traversal yang dipilih.

4. Pohon Ekspresi (Expression Tree)

Ekspresi aritmetika dapat direpresentasikan sebagai pohon biner: operator di simpul internal, operand di daun. Contoh: (3 + 4) × (5 − 2)

Preorder (prefix): × + 3 4 − 5 2

Inorder (infix): 3 + 4 × 5 − 2 (perlu kurung: (3+4)×(5−2))

Postorder (postfix/RPN): 3 4 + 5 2 − × (dipakai HP calculator)

5. Pohon Merentang Minimum (MST)

Definisi

Pohon merentang (spanning tree) dari graf G adalah subgraf yang merupakan pohon dan menghubungkan semua simpul G. Graf dengan n simpul memiliki spanning tree dengan tepat n−1 sisi.

MST (Minimum Spanning Tree) adalah pohon merentang dengan total bobot sisi minimum. Aplikasi: jaringan komputer (kabel minimum), jaringan distribusi listrik, clustering.

Algoritma MST: Kruskal vs Prim

Urutkan semua sisi berdasarkan bobot (ascending).
Untuk setiap sisi: tambahkan ke MST jika tidak membentuk sirkuit (Union-Find).
Berhenti ketika MST memiliki n-1 sisi.

Kompleksitas: O(E log E)

Cocok untuk sparse graph. Gunakan Union-Find dengan path compression.

Visualisasi MST (Animasi Pertumbuhan Pohon)

MST (hijau) dipilih Kruskal: DA(2), DC(3), CE(4), CB(5). Total = 14. Animasi menunjukkan pertumbuhan MST.

6. Pohon Huffman (Kompresi Data)

Algoritma Huffman (Optimal Prefix Code)

Simbol sering muncul mendapat kode pendek; simbol jarang mendapat kode panjang. Dijamin prefix-free (tidak ada kode yang merupakan prefix kode lain) dan optimal untuk distribusi frekuensi yang diberikan.

Hitung frekuensi setiap simbol.
Bangun min-heap berisi semua simbol sebagai pohon berukuran 1.
Ambil dua pohon frekuensi terkecil; gabungkan menjadi pohon baru (frekuensi = jumlah).
Masukkan pohon gabungan ke heap; ulangi sampai tersisa satu pohon.
Beri label sisi kiri=0, kanan=1. Kode = label path dari akar ke daun.

Demo: Frekuensi Simbol

Frekuensi (urut menurun) — kandidat kode Huffman:

'A'

f=3

kode pendek

'B'

f=2

kode medium

'C'

f=1

kode panjang

Simbol frekuensi tertinggi mendapat kode terpendek dalam pohon Huffman optimal.

7. B-Tree dan Merkle Tree

B-Tree (Basis Data)

Generalisasi BST di mana setiap simpul dapat memiliki banyak anak (bukan hanya 2). B-tree orde m: setiap simpul internal memiliki ⌈m/2⌉ hingga m anak.

Tinggi h = O(log_b n) di mana b bisa 100-1000 → hanya 3-4 level untuk miliaran record.

PostgreSQL, MySQL, MongoDB menggunakan B+tree untuk semua indeks.

Merkle Tree (Pohon Hash)

Pohon biner di mana daun = hash blok data, simpul internal = hash(anak kiri || anak kanan). Akar = Merkle root.

Verifikasi keanggotaan (Merkle proof) hanya butuh O(log n) hash — sangat efisien.

Digunakan: Git (verifikasi integritas commit), IPFS, sistem berkas ZFS, dan replikasi basis data terdistribusi.

Koneksi ke Ilmu Komputer

Pohon Merkle & Integritas Data: Git menyimpan setiap commit sebagai pohon hash. Mengubah satu berkas mengubah hash induknya sampai ke akar, sehingga kerusakan data langsung terdeteksi. Sistem berkas ZFS memakai prinsip yang sama.

Trie (Pohon Prefiks): Menyimpan pasangan kunci-nilai berdasarkan awalan kunci, sehingga pencarian bergantung pada panjang kunci, bukan jumlah data. Dipakai untuk autocomplete, kamus, dan tabel perutean IP.

Decision Tree Lower Bound: Sorting berbasis perbandingan dapat dimodelkan sebagai pohon keputusan biner. Karena daunnya minimal n!, tinggi minimum = log₂(n!) = Ω(n log n) — bukti formal mengapa heapsort/mergesort optimal.

9. Contoh Soal & Pembahasan

Soal 1: Sifat Pohon

Sebuah pohon memiliki 100 simpul. Berapa banyak sisinya?

Soal 2: Traversal

Diberikan ekspresi 7 + 3 × (5 − 2). Buatlah pohon ekspresi dan tuliskan postorder-nya.

Soal 3: MST Kruskal

Graf 5 simpul, sisi (bobot): AB=1, AC=4, BC=2, BD=5, CD=3, CE=6, DE=7. Tentukan MST Kruskal.

Soal 4: Huffman

Bangun kode Huffman untuk: A:5, B:9, C:12, D:13, E:16, F:45.

Soal 5: BST Insertion & Inorder

Sisipkan berurutan 50, 30, 70, 20, 40, 60, 80 ke BST kosong. Tuliskan inorder traversal.

Soal 6: Merkle Tree Proof

Pohon Merkle dengan 8 data leaf {d1,...,d8}. Berapa node hash yang diperlukan untuk memverifikasi d3 ada di root?

← Graf Kompleksitas Algoritma →

Munir, R. (2020). Matematika Diskrit, Edisi 7, Penerbit Informatika ITB, Bab 10. — Rosen, K. H. (2019). Discrete Mathematics and Its Applications, 8th ed., Ch. 11. — Cormen, T. H. et al. (2022). Introduction to Algorithms, 4th ed., MIT Press, Ch. 12, 21.

Bank Soal Multi-Kompleksitas & Kasus Terintegrasi

Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 10 — Pohon (Trees).

MUDAH Soal Dasar Struktur Pohon

T-M1: Properti Pohon

Pohon T memiliki 8 vertex. Berapa jumlah sisi (edges)? Berapa sisi yang harus ditambah/hapus agar menjadi spanning tree dari K₄?

T-M2: Traversal Pohon

BST dengan inorder traversal menghasilkan {1,3,5,7,9}. Root=5. Gambarkan satu kemungkinan BST dan tulis preorder traversal-nya.

T-M3: Height & Complete Binary Tree

Complete binary tree dengan 15 node. Berapa height-nya? Berapa leaf node? Berapa internal node?

T-M4: Minimum Spanning Tree

Graf berbobot: V={A,B,C,D}, E={AB:4, AC:2, AD:7, BC:1, BD:5, CD:3}. Temukan MST menggunakan Kruskal's algorithm.

SEDANG BST & Huffman

T-S1: BST Insertion & Search Complexity

Masukkan {50,30,70,20,40,60,80} ke dalam BST secara berurutan. Berapa tinggi BST? Apakah balanced? Berapa perbandingan untuk search 40?

T-S2: Huffman Coding

Frekuensi karakter: A=45, B=13, C=12, D=16, E=9, F=5. Bangun Huffman tree. Berapa bit rata-rata per karakter? Bandingkan dengan fixed-length encoding.

T-S3: Spanning Tree Count

Berapa banyak spanning tree yang berbeda pada K₄? Gunakan Cayley's formula: n^(n-2).

T-S4: AVL Tree Rotation

BST dengan node {10,20,30} diinsert berurutan. BST menjadi right-skewed. Tunjukkan single left rotation untuk balance AVL tree.

SULIT Pohon Lanjut & Cryptographic Trees

T-H1: B-Tree Insertion

B-tree orde 3 (max 2 keys per node). Insert {10,20,5,6,12,30,7} secara berurutan. Tunjukkan split yang terjadi dan struktur akhir B-tree.

T-H2: Huffman + Entropy Coding

Sebuah sumber pesan memiliki simbol {a:0.5, b:0.25, c:0.125, d:0.125}. Hitung entropy H(S). Bangun Huffman code dan hitung expected code length. Verifikasi keoptimalan vs entropy.

T-H3: Red-Black Tree Properties

Sebutkan 5 properti Red-Black tree. Buktikan bahwa RB tree dengan n node memiliki height ≤ 2·log₂(n+1).

TERINTEGRASI BST + Complexity, Huffman + Entropy, Merkle + Cryptography

T-T1: BST + Complexity — Worst vs Average Case

Bandingkan kompleksitas BST vs AVL tree untuk operasi search dengan n=10⁶ elemen. Jika BST dalam worst case (sorted input), berapa perbandingan? Berapa untuk AVL? Berapa speedup?

T-T2: Pohon Merkle — Bukti Keanggotaan

Sebuah pohon Merkle menaungi 1024 blok data. (a) Berapa total simpulnya? (b) Berapa hash yang diperlukan untuk membuktikan satu blok termasuk di dalamnya? (c) Jika satu blok berubah, berapa simpul yang harus dihitung ulang?

T-T3: Pohon + Perhitungan pada Pohon Biner Penuh

Sebuah pohon Merkle berupa pohon biner penuh dengan tinggi H = 20 dipakai untuk memverifikasi integritas blok data. (a) Berapa banyak daun (blok data)? (b) Berapa total simpul? (c) Berapa simpul yang perlu dikirim untuk membuktikan satu blok termasuk di dalamnya?