Tree
Tree
Struktur Pohon & Kunjungan Pohon Biner
Definisi Pohon (Tree)
Pohon (Tree) termasuk struktur non linear yang didefinisikan sebagai data yang teroganisir dari suatu item informasi cabang yang saling terikat
Istilah dalam pohon
1. Predesesor
Node yang berada diatas node tertentu.
(Contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu
(Contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
(Contoh : A dan B merupakan ancestor dari F)
4. Descendant
Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama
(Contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node
(Contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node
(Contoh : F merupakan childe dari F)
7. Sibling
Node yang memiliki parent yang sama dengan satu node
(Contoh : E dan F adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta descendant-nya
(Contoh : Subtree B, E, F dan subtree D, G, H)
9. Size
Banyaknya node dalam suatu tree
(Contoh : Gambar tree diatas memiliki size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree
(Contoh : gambar tree diatas memiliki height = 3)
11. Root
Node khusus dalam tree yang tidak memiliki predesesor
(Contoh : A)
12. Leaf (Daun)
Node - Node dalam tree yang tidak memiliki daun
(Contoh : Node E, F, C, G, H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node
(Contoh : Node A memiliki derajat 3, node B memiliki derajat 2)
Istilah Istilah Dasar
Pohon atau tree adalah salah satu bentuk graph terhubung yang tidak mengandung sirkuit
Karena merupakan Graph terhubung, maka pada Pohon(Tree) selalu terdapat Path atau Jalur yang menghubungkan setiap simpul dalam dua pohon.
Pohon (Tree) dapat juga didefinisikan sebagai kumpulan elemen yang salah satu elemenya disebut dengan akar (root) dan sisa elemen lain (Simpul) yang terpecah menjadi sejumlah himpunan yang saling tidak berhubungan yang disebut dengan Subpohon (Subtree) atau cabang
Sifat Utama Pohon Berakar
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2. Mempunyai simpul khusus yang disebut Root, Jika simpul tersebut memiliki derajat keluar >= 0, dan derajatnya masuk = 0
3. Mempunyai simpul yang disebut sebagai Daun/.Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 14. Setiap simpul mempunyai Tingkatan/Level yang dimulai dari root yang levelnya = 1 sampai dengan level ke- n pada daun paling bawah. Simpul yang mempunyai level sama disebut bersaudara atau Sibling
5. Pohon mempunyai ketinggian atau kedalaman atau Height, yang merupakan level tertinggi
6. Pohon mempunyai Weight atau berat atau bobot, yang banyaknya daun (Leaf) pada pohon.
7. Banyaknya Simpul maksimum sampai Level N adalah :
8. Banyaknya simpul untuk setiap level I adalah:
Hutan (Forest) adalah kumpulan Pohon yang tidak saling berhubungan
Diketahui suatu bentuk Pohon berakar T sebagai berikut :
Pohon diatas mempunyai:
a. Simpul sebanyak = 8 dan edge = n - 1 = 8 - 1 = 7
b. Root pada Pohon T diatas adalah simpul P
c. Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W
d. Level (tingkatan) Pohon = 4 yaitu:
Level 1 = Simpul p
Level 2 = Simpul q dan t
Level 3 = Simpul r, s, dan u
Level 4 = simpul v dan w
e. Ketinggian atau kedalaman = jumlah level = 4
f. Weight atau berat atau bobot = Jumlah daun = 4
Dalam gambar pohon T diatas dapat dibentuk 2 buah hutan (forest), bila simpul P dihilangkan, yaitu :
Hutan 1: Q,R,S
Hutan 2: T,U,V,W
g. Banyaknya simpul maksimum yang dapat terbentuk sampai Level 4 (bila simpul pada pohon dianggap penuh) adalah : 
a. Kunjungi Cabang Kiri
h. Banyaknya simpul maksimum untuk setiap Level I (Bila simpul pada pohon dianggap penuh) adalah:
Maksimum Simpul pada level 2 = 2 (I - 1)
= 2 (2-1) = 2
Maksimum Simpul pada level 3 = 2 (3-1) = 4
Maksimum simpul pada level 4 = 2 (4-1) = 8
Pohon Binar (Binary Tree)
Struktur ini biasanya digunakan untuk menyajikan data yang mengandung hubungan hirarkial antara elemen - elemennya.
Bentuk Pohon Berakar yang lebih mudah dikelola dalam komputer adalah pohon biner (Binary tree) yang lebih dikenal sebagai Pohon Umum (General Tree) yang dapat didefinisikan sebagai kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan Subpohon Kiri / cabang kiri ( Left Subtree) dan Subpohon kanan / Cabang kanan (Right Subtree)
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap simpul paling banyak hanya memiliki dua buah anak
2. Derajat tertinggi dari setiap Simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimungkinkan tidak mempunyai simpul
Berikut ini diberikan contoh gambar pohon binar (Binary tree) dengan cabang kiri dan cabang kanan
Istilah Pada Pohon Biner
Pohon Biner Penuh (Full Binary Tree)
Semua simpul (kecuali daun) memiliki 2 Anak dan tiap cabang memiliki panjang ruas yang sama
Pohon Biner Lengkap (Complete Binary Tree)
Hampir sama dengan pohon biner penuh, semua simpul (kecuali daun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda
Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda
Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang sama
Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak/turunan kecuali daun
Penyajian Pohon Binar (Binary Tree)
Tree dapat dibuat dengan menggunakan linked list secara rekursif.
Linked list yang digunakan adalah double linked list non circular
Data yang pertama kali masuk akan menjadi node root
Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari node root, akan masuk dan menmpati node di sebalah kanan node root
Bila diberikan untai HAKJCBL, maka proses untuk membentuk pohon biner dari untai diatas adalah:
1. Karakter pertama 'H' ditempatkan sebagai akar (root)
2. Karakter 'A', karena lebih kecil dari 'H', maka akan menempati cabang kiri
3. Karakter 'K', karena lebih besar dari 'H', maka akan menempati cabang kanan
4. Karakter 'J', lebih besar dari 'H' dan kecil dari 'K', maka menempati cabang kiri'K'
5. Karakter 'C', karena lebih besar dari 'A', maka akan menempati cabang kanan
6. Karakter 'B', karena lebih kecil dari 'C', maka akan menempati cabang kiri
7. Karakter 'L', lebih besar dari 'K', maka menempati cabang kiri kanan
Sehingga terbentuk pohon biner seperti ini:
Latihan
Buatlah Pohon Biner dari barisan bilangan berikut:
1. 12, 22, 8, 19, 10, 9, 20, 4, 2, 6
2. 2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 7
3. 7, 13, 4, 6, 5, 9, 15, 20, 60, 14, 40, 70
4. 50, 45, 55, 40, 60, 70, 35, 30, 20, 80, 75, 85
5. 12, 11, 17, 19, 21, 20, 22, 13, 14, 18, 16, 15
Kunjungan Pada Pohon Binar
Kunjungan pada pohon binar merupakan salah satu operasi yang sering dilakukan pada suatu pohon binar tepat satu kali (Binary Tree Traversal). Operasi ini terbagi menjadi 3 bentuk:
1. Kunjungan secara Preorder (Depth First Order)
Mempunyai aturan:
a. Cetak isi simpul yang dikunjungi (Simpul Akar)
b. Kunjungi Cabang Kiri
c. Kunjungi Cabang Kanan
2. Kunjungan secara InOrder (Symetric Order), mempunyai urutan:
b. Cetak isi simpul yang dikunjungi (Simpul Akar)
c. Kunjungi Cabang Kanan
3. Kunjungan secara PostOrder, mempunyai aturan:
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
Pada ketiga cara kunjungan diatas, kunjungan ke Cabang Kiri dilakukan terlebih dahulu, baru kemudian kunjungan ke cabang kanan. dengan orientasi semacam ini, Ketiga kunjungan diatas disebut dengan Left to Right Oriented (LRO).
Jika kunjungan ke cabang kanan dilakukan lebih dahulu baru kemudian kunjungan ke Cabang Kiri, maka Orientasi semacam ini disebut Right To Left Oriented (RLO)
1. Kunjungan secara PreOrder (Depth First Order), mempunyai urutan:
a. Cetak isi simpul yang dikunjungi (Simpul Akar)
b. Kunjungi Cabang Kiri
c. Kunjungi Cabang Kanan
2. Kunjungan secara InOrder (Symetric Order), Mempunyai urutan:
a. Kunjungi Cabang Kiri
b. Cetak isi simpul yang dikunjungi (Simpul Akar)
c. Kunjungi Cabang Kanan
3. Kunjungan secara PostOrder, mempunyai urutan:
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
Latihan
Sebutkan Kunjungan pohon biner secara Preorder, Inorder, PostOrder dari bentuk pohon biner dibawah ini
1.
2.
Komentar
Posting Komentar