TREE [Struktur Data]

Assalamualaikum Wr.Wb

Halo teman teman semuaa, pasti masih semangat kan yaa?? Hemm jadi aku mau ngebahas struktur data materi tree. Yuk kita pelajari apasih tree itu?

Tree adalah kumpulan node yang saling terhubung satu sama lain. Dalam suatu kesatuan yang membentuk layaknya struktur sebuah pohon.

Nah sedangkan struktur pohon itu adalah suatu cara mempresentasikan suatu struktur hiarki(one to many)

Tree dibagi menjadi 2 yaitu

1.      Tree statik       : isi node – nodenya tetap karena bentuk pohonnya sudah ditentukan

2.      Tree dinamik   : isi nodenya berubah ubah karena terjadi proses penambahan (insert) dan penghapusan (delete)

Ø Node root

           Node root dalam tree adalah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node node anak. Semua node dapat ditelusuri dari node root tersebut. Node node lain di bawah node root saling terhubung satu sama lain dan disebut subtree.

Ø Implementasi Tree

Contoh penggunaan struktur pohon:

-          Silsilah keluarga

-          Parse tree

-          Struktur file

-          Pertandingan

           

            Contoh Tree

Ø Representasi Tree

Tingkat terahir yang tidak memiliki anak itu adalah datanya.

Ø  Terminologi Tree

·         Predecesor

Node yang berada diatas node tertentu.

Contoh :

Untuk contoh kita bisa lihat dari gambar pada representasi tree diatas yaitu C adalah prodecesor dari F, G, H.

·         Successor

Node yang berada dibawah node tertentu.

Contoh :

Pada gambar diatas kita lihat, F adalah successor dari C dan sebagainya

·         Ancestor

Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

Contoh :

Anestor J adalah E, B, A.

·         Descendant

Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama.

Contoh : (A, B, D), (B, E, I ) dan selanjutnya.

·         Parent

Predecessor satu level diatas suatu node

Contoh :

-F parent C

-G parent C

-H parent C

·         Child

Successor satu level dibawah suatu node

Contoh :

-Child dari C adalah F,G,H

-Child dari B adalah D,E

-Child dari E adalah I,J

·         Sibling

Node node yang memiliki parent yang sama

Contoh :

-D sibling E

-F sibling G sibling H

·         Size

Banyaknya node dalam suatu tree

Contoh :

Nah dapat dilihat pada tabel diatas sizenya adalah 10

·         Height

Banyaknya tingkatan dalam suatu tree

Contoh :

Height pada gamar diatas 4 karena tingkat dimulai dari 0

·         Leaf

Node node dalam tree yng tidak memiliki successor(tidak memiliki child/anak)

Contoh :

Pada gambar diatas yang tidak memiliki anak yaitu I,J dan F,G,H.

·         Degree

Banyaknya child dalam suatu node

Contoh :

-C degree 3

-B degree 2

-E degree 2

Ø  Jenis Tree

1.    Binary Tree

Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree dan kedua subtree tersebut harus terpisah. Tidap node pada binary tree hanya boleh memiliki paling banyak 2 child.

Contoh :

·         Full binary tree

Semua node (kecuali leaf) pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama.

Contoh :

·         Skewed Tree

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki 1 anak.

Contoh :

·         Representasi Binary Tree pada Array

-          Index dari array menunjukkan nommor node

-          Index ke-0 merupakan root

-          Index dari left child adalah 2p + 1, dimana  p = index dari parent

-          Index dari right child adalah 2p - 2, dimana  p = index dari parent

-          Index dari parent adalah (p – 1)/2

ü  Latihan soal !

Cara penyelesaian

A = Root

B = 2p + 1 = 2(0)+1

                   = 1

C = 2p + 2 = 2(0)+2

                   = 2

D = 2p + 1 = 2(1)+1

                   = 3

E = 2p + 1 = 2(2)+1

                   = 5

F = 2p + 2 = 2(2)+2

                   = 6

G = 2p + 1 = 2(3)+1

                   = 7

H = 2p + 1 = 2(5)+1

                   = 11

I = 2p + 2 = 2(5)+2

                   = 12

I = 2p + 2 = 2(6)+2

                   = 14

Hasil:

·         Konverensi array terurut ke binary tree

Jika data ganjil,maka Child sebelah kiri lebih kecil dari parent(kanan), dan berlaku sebaliknya.

Jika data genap maka kita dapat menggunakan rumus : n/2+1 atau n/2-1

Contoh :

ü  LATIHAN SOAL!

Terimakasih telah menyimak dan semoga dapat dipahami dengan mudah, sekian materi tentang tree ini

Wassalamualaikum.Wr.Wb