📋 Daftar Isi
Pohon Biner
Pohon biner adalah pohon n-ary dengan n = 2. Merupakan pohon yang paling penting karena banyak aplikasinya. Setiap simpul di dalam pohon biner mempunyai paling banyak 2 buah anak. Dibedakan antara anak kiri (left child) dan anak kanan (right child). Karena ada perbedaan urutan anak, maka pohon biner adalah pohon terurut.
Keterangan: Dua buah pohon biner yang berbeda
Keterangan: Pohon biner penuh
Pohon Biner Seimbang
Pada beberapa aplikasi, diinginkan tinggi upapohon kiri dan tinggi upapohon kanan yang seimbang, yaitu berbeda maksimal 1.
Keterangan: T1 dan T2 adalah pohon seimbang, sedangkan T3 bukan pohon seimbang.
Terapan Pohon Biner
Pohon Ekspresi
Pohon ekspresi dari (a + b)*(c/(d + e))
daun → operand
simpul dalam → operator
Pohon Keputusan
Contoh: klasifikasi vertebrata
Kode Awalan
Pohon biner dari kode prefiks {000, 001, 01, 10, 11}
Kode Huffman
.tg {border-collapse:collapse;border-spacing:0;} .tg td{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;word-break:normal;} .tg th{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;font-weight:normal;overflow:hidden;padding:10px 5px;word-break:normal;} .tg .tg-c3ow{border-color:inherit;text-align:center;vertical-align:top} .tg .tg-ihkz{border-color:inherit;text-align:center;vertical-align:top}| Kode ASCII | |
|---|---|
| Simbol | Kode ASCII |
| A | 01000001 |
| B | 01000010 |
| C | 01000011 |
| D | 01000100 |
rangkaian bit untuk string ‘ABACCDA’:
01000001010000010010000010100000110100000110100010001000001
atau 7 × 8 = 56 bit (7 byte).
Tabel kekerapan (frekuensi) dan kode Huffman untuk string ABACCDA
| Simbol | Kekerapan | Peluang | Kode Huffman |
| A | 3 | 3/7 | 0 |
| B | 1 | 1/7 | 110 |
| C | 2 | 2/7 | 10 |
| D | 1 | 1/7 | 111 |
Algoritma pembentukan pohon Huffman
- Pilih dua simbol dengan peluang (probability) paling kecil (pada contoh di atas simbol B dan D). Kedua simbol tadi dikombinasikan sebagai simpul orangtua dari simbol B dan D sehingga menjadi simbol BD dengan peluang 1/7 + 1/7 = 2/7, yaitu jumlah peluang kedua anaknya.
- Selanjutnya, pilih dua simbol berikutnya, termasuk simbol baru, yang mempunyai peluang terkecil.
- Ulangi langkah 1 dan 2 sampai seluruh simbol habis.
Pohon Pencarian Biner
Kunci(T1) < Kunci(R)
Kunci(T2) > Kunci(R)
Contoh:
50, 32, 18, 40, 60, 52, 5, 25, 70
Sumber : Buku Matematika Diskrit (Rinaldi Munir)
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Pohon, daftar lengkapnya adalah sebagai berikut.
