Tree

pada tanggal

Binary Tree

Definisi Pohon (Tree)

Pohon (Tree) termasuk struktur non linear yang didefinisikan sebagai data yang terorganisir dari suatu item informasi cabang yang saling terkait.



Istilah dalam pohon (tree)


  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 child dari B)
  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 (Akar) : 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 elemennya 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      derajat masuk = 0.
  3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan             berderajat masuk = 1.
  4. 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 Brother atau Stribling.
  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 :
    2 (N)  - 1
  8. Banyaknya Simpul untuk setiap Level I adalah :

                                        N 
                   å    2 ( I – 1)
                                        I = 1 
Hutan (Forest) adalah kumpulan Pohon yang tidak saling berhubungan.


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 Biner (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.


Algoritma Binary Tree Traversal 


Proses traversal adalah proses melakukan kunjungan pada setiap node pada suatu binary tree tepat satu kali. Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. 

Terdapat tiga teknik rekursif untuk binary tree traversals ,yaitu: 

  1. Mengunjungi simpul akar (root), 
  2. Melakukan traversal subpohon kiri (left subtree), dan 
  3. Melakukan traversal subpohon kanan (right subtree). 

Yang membedakan antara teknik satu dengan yang lain adalah proses pengurutan tugas mereka. 

Terdapat tiga cara untuk melakukan kunjungan itu, yaitu: 

1. Traversal preorder (depth first order) 

    Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan. Algoritma umum traversal preorder adalah sebagai berikut: 

  • Jika tree kosong, maka keluar 
  • Proses node root.  
  • Traverse subtree kiri secara preorder. 
  • Traverse subtree kanan secara preorder. 

2. Traversal inorder (symmetric order) 

    Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan. Algoritma umum traversal inorder adalah sebagai berikut: 

  • Jika tree kosong, maka keluar. 
  • Traverse subtree kiri secara inorder. 
  • Proses node root. 
  • Traverse subtree kanan secara inorder. 

3. Traversal postorder 

    Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi. Algoritma umum traversal inorder adalah sebagai berikut: 

  • Jika tree kosong, maka keluar. 
  • Traverse subtree kiri secara postorder. 
  • Traverse subtree kanan secara postorder. 
  • Proses node root.

Komentar

Posting Komentar