Hai kawan! Pada saat ini saya akan membahas mengenai "TREE"
Tree adalah kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layaknya struktur sebuah pohon. Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarkis (hubungan one to many) secara grafis yang mirip sebuah pohon,walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah, Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one to many) dan tidak linier antara elemen-elemennya.
Tree Statik adalah isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan.
Tree Dinamik adalah isi node-nodenya berubah-ubah karena proses penambahan (insert) dan penghapusan (delete).
Node Root dalam tree adalah suatu node yang memiliki hirarkis tertinggi dan dapat juga memiliki node-node anak. Semua node dapat ditelusuri dari node root tersebut. Node Root adalah node khusus yang tercipta pertama kali. Node-node lain dibawah node root saling terhubung satu sama lain dan disebut subtree.
Terminologi Tree
1. Predecesor adalah node yang berada diatas node tertentu.
2. Successor adalah node yang berada dibawah node tertentu.
3. Ancestor adalah seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant adalah seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang
sama.
5. Parent adalah predecessor satu level diatas suatu node.
6. Child adalah Successor satu level dibawah suatu node.
7. Sibling adalah node-node yang memiliki parent yang sama.
8. Subtree adalah suatu node beserta descendantnya.
9. Size adalah banyaknya node dalam suatu tree.
10. Height adalah banyaknya tingkatkan dalam suatu tree.
11. Root adalah node khusus yang tidak memiliki predecessor.
12. Leaf adalah node-node dalam tree yang tidak memiliki successor.
13. Degree adalah banyaknya child dalam suatu node.
Implementasi Tree
Contoh penggunaan struktur pohon :
1. Sisilah keluarga.
2. Parse Tree (pada compiler).
3. Struktur File.
4. Prebandingan.
Jenis-jenis Tree
1. Binary Tree adalah suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
Node pada binary tree.
1. Jumlah maksimum node pada setiap tingkat adalah 2n
2. Node pada binary tree maksimum berjumlah 2 n-1
Representasi binary tree pada array
1. Index dari array merepresentasikan atau menunjukkan nomor node.
2. Index ke-0 merupakan root.
3. Index dari left child adalah 2p + 1, dimana p = index dari parent.
4. Index dari right child adalah 2p + 2, dimana p = index dari parent.
5. Index dari parent adalah (p-1)/2.
Contoh binary tree:
Jika tanda panah kekanan maka menggunakan rumus 2p + 2 dan jika tanda panah kekiri maka menggunakan rumus 2p +1.
A = Root
B = 2p + 1
= 2(0) + 1
= 1
D = 2p + 1
= 2(1) + 1
= 3
E = 2p + 1
= 2(2) + 1
= 5
G = 2p + 1
= 2(3) + 1
= 7
H = 2p + 1
= 2(5) + 1
= 11
C = 2p + 2
= 2(0) + 2
= 2
F = 2p + 2
= 2(2) + 2
= 6
I = 2p + 2
= 2(5) +2
= 12
J = 2p + 2
= 2(6) +2
= 14
K = 2p + 2
= 2(11) + 2
= 24
Dari materi diatas, Semoga bermanfaat.
Wassalamualaikum.Wr.Wb
