Struktur Data Tree

Pengertian TREE

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.

Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

Istilah-istilah umum dalam TREE

1. Prodecessor : node yang berada diatas node tertentu.
2. Successor : node yang berada di bawah node tertentu.
3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. Parent : predecssor satu level di atas suatu node.
6. Child : successor satu level di bawah suatu node.
7. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
8. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik   dari tree tersebut.
9. Size : banyaknya node dalam suatu tree.
10. Height : banyaknya tingkatan/level dalam suatu tree.
11. Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
12. Leaf : node-node dalam tree yang tak memiliki seccessor.
13. Degree : banyaknya child yang dimiliki suatu node.

Jenis Jenis TREE

1.  Binary Tree

                Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

Jenis-jenis Binary Tree :

•       Full Binary Tree

                Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

              

Full Binary Tree

•       Complete Binary Tree

                Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

            

Complete Binary Tree

•       Skewed Binary Tree

                Yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

             

Skewed Binary Tree

Operasi-Operasi Pada Binary Tree :

• Create : Membentuk binary tree baru yang masih kosong.

• Clear : Mengosongkan binary tree yang sudah ada.

• Empty : Function untuk memeriksa apakah binary tree masih kosong.

• Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

• Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

• Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

• Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

•  DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

•  Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

• Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

   2.     Tree Traversal

                Ada tiga pola umum yang digunkaan untuk mengunjungi semua node dalam tree.

Perbedaan antara 3 pola ini adalah urutan kunjungan terhadap node. Kunjungan   ini dinamakan “traversal.”, yaitu preorder, inorder dan postorder.

Tree Traversal

• Preorder : Penelusuran node berawal dari ROOT, kemudian berlanjut ke turunan dari sebelah kiri, jika sedah jalur kiri sudah tidak ada anak lagi, diteruskan ke jalur turunan sebelah kanan, terus berlanjut sampai akhir node. Atau pertama menujuke node ROOT kemudian secara recursive melakukan preorder pada subtree sebelah kiri, diikuti dengan traversal preorder secara recursive ke subtree sebelah kanan.

• Inorder : Melakukan traversal inorder secara recursive pada subtree sebelah kiri, menuju ke node ROOT, dan terakhir melakukan traversal inorder secara recursive pada subtree sebelah kanan.

• Postorder : Melakukan traversal postorder secara recursive pada subtree bagian kiri dan kanan diikuti dengan berkunjung ke node ROOT.

perhatikan contoh operasi-operasi pada Binary Tree berikut ini :

Gambar 1 :

Gambar 2 :

Gambar 3 :