STRUKTUR DATA - Tree

Assalamualaikum Wr.Wb

Hay kawan kawan kali ini saya akan membahas tentang Tree kira kira apa ya itu?. Yaudah kita bahas yuk!!

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

contoh tree

 

  

Tree ada 2

1.      Tree Statik

Isi node nodenya tetap karena bentuk pohonnya sudah di tentukan

2.      Tree Dinamik

Isi nodenya berubah ubah karena proses penambahan dan penghapusan

Contoh penggunaan Tree dengan struktur pohon biasanya ada di:

-          Silsilah Keluarga

-          Parse Tree(pada Kompiler)

-          Struktur file

-          Pertandingan

TREE

Keterangan

-          Node root = Sebuah node khusus yang tercipta pertama kalinya / suatu node yang memliki
                        hirkaki tertinggi dan dapat juga memiliki node node anak

-          Sub Tree = Node node yang berada di bawah node root/ anak dari node root

-          Data/IF = Data terakhir dalam Tree, berisi data yang akan bita ambil

Representasi Tree

 

Istilah Istilah dalam TREE

 

1.       Predesesor = Node yang berada diatas node tertentu.

(contoh :  B predesesor dari B dan C).

2.       Succesor = Node yang berada dibawah node tertentu.
c                       contoh :  B dan C merupakan succesor dari A).

3.       Ancestor = Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.                           (contoh :  D merupakan Ancestor dari C dan A).

4.       Parent = Predesesor satu level diatas satu node
                      (contoh : C merupakan parent dari D,E,F).

5.       Child = Succesor satu level dibawah satu node
                    (contoh : C merupakan child dari D,E,F)

6.       Sibling = Node yang memiliki parent yang sama
                       (contoh :D,E,F merupakan Sibling)

7.       Subtree = Bagian dari tree yang berupa suatu node beserta descendant-nya
                        (contoh : Subtree B, E, F dan Subtree  D, G, H)

8.       Size = Banyaknya node dalam suatu tree
                   (contoh : gambar tree diatas memiliki size = 10)

9.       Height = Banyaknya tingkat/level dalam suatu tree

                (contoh : gambar tree diatas memiliki height = 4)

10.   Root (Akar) = Node khusus dalam tree yang tidak memiliki predesesor

                        (Contoh : A)

11.   Leaf (Daun) = Node-node dalam tree yang tidak memiliki daun

                        (contoh : D,I,J,F,G,H)

12.   Degree (Derajat) = Banyaknya child yang dimiliki oleh suatu node

                                (contoh : Node B memiliki derajat 2, node C memiliki derajat 3)

Reprentasi Binary Tree pada Array

Keterangan :

-          Root = = Sebuah node khusus yang tercipta pertama kalinya

-          Left Child = maksudnya adalah posisi sebelah kiri dari root ataupun Parent

-          Right Child = maksudnya adalah posisi sebelah kanan dari root ataupun Parent

  

Penulisan Tree dalam Array ada syarat2 khusus yang harus kita lakukan:

-          Index ke-0 merupakan Root

-          Cara mencari indeks dari Left Child adalah

   Dimana: P adalah Indeks atau Parent

-          Cara mencari indeks dari Right Child adalah

      

                     

   Dimana: P adalah Indeks atau Parent

-          Cara mengubah tree ke array, usahakan parent dari Child harus kia ketahui terlebih dahulu terletak para indeks ke berapa

Contoh:

 

Jawab :

Cara mengerjakan

1.       Kita harus menaruh root pada indeks petama

2.       Kita harus menentukan tree diatas bagian left atau right, setelah kita tau posisi node2 tree maka kita bias menghitung menggunakan rumus yang ada.
ingat : kita bias menghitung jika letak indeks array parent Sudah kita ketahui.

Left Child (2P+1)	Right Child (2P+2)
B  = 2P + 1  = 2(0) + 1  = 1 (Terletak di Indeks ke-1)	C  = 2P + 2      = 2(0) + 2      =  2 (Terletak di Indeks ke-2)
D  = 2P + 1   = 2(1) + 1   = 3 (Terletak di Indeks ke-3)	F   = 2P + 2      = 2(2) + 2      = 6 (Terletak di Indeks ke-6)
E  = 2P + 1   = 2(2) + 1   = 5 (Terletak di Indeks ke-5)	I   = 2P + 2     = 2(5) + 2     = 12 (Terletak di Indeks ke-12)
G  = 2P + 1   = 2(3) + 1      = 7 (Terletak di Indeks ke-7)	J  = 2P + 2                 = 2(2) + 2                   = 14 (Terletak di Indeks ke-14)
H  = 2P + 1   = 2(5) + 1      = 11 (Terletak di Indeks ke-11)	K  = 2P + 2                 = 2(11) + 2                   = 24 (Terletak di Indeks ke-24)

Hasilnya :

Sekian dulu ya pembahasan kali ini tentang Tree. Semoga bermanfaat ^_^

wassalamualaikum Wr.Wb