Binary Tree

Assalamualaikum wr.wb

Hy eman- teman kali ini saya akan membahas tentang “TREE”.

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. 

Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam Tree :

a) Prodecessor              : node yang berada diatas node tertentu.

      b) Successor                 : node yang berada di bawah node tertentu.

c) Ancestor                   : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur

                                                                yang sama

d) Descendant              : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur

                                                                           yang sama.

e) Parent                      : predecssor satu level di atas suatu node.

f) Child                        : successor satu level di bawah suatu node.

g) Sibling                     : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree                    : bagian dari tree yang berupa suatu node beserta descendantnya

 dan memiliki semua karakteristik dari tree tersebut.

i) Size                          : banyaknya node dalam suatu tree.

j) Height                      : banyaknya tingkatan/level dalam suatu tree.

k) Root                        : satu-satunya node khusus dalam tree yang tak punya predecssor.

l) Leaf                         : node-node dalam tree yang tak memiliki seccessor.

m) 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.

-          Representasi Binary Tree Pada Array

·         Index dari Array mempresentasikan atau menunjukkan nomor 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 = indekx dari parent

·         Index dari Parent adalah (p-1)/2

Catatan : Lihat arah tanda panah jika ke kanan rumusnya adalah (2p + 2) dan jika ke kiri (2p + 1)

Cara Penyelesaian :

                                    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

                                    J = 2p + 2

                                       = 2(6) + 2 = 14

                                    K = 2p + 2

                                        = 2(11) + 2 = 24  

                        9 = 2p+1

                              2(0) + 1 = 1

                       

                        88 = 2p+2

                             = 2(0) + 2 =2

8 = 2p + 1

                            = 2(1) + 1 = 3

                        10 = 2p + 2

                            = 2(01 + 2 = 4

                        51 = 2p + 1

                            = 2(2) + 1 = 5

                        89 = 2p + 2

                            = 2(2) + 2 = 6

                        2 = 2p + 1

                           = 2(3) + 1 = 7

                        15 = 2p + 2

     = 2(4) + 2 = 10

                        22  = 2p + 1

                             = 2(5) + 1 = 11 

Demikian yg dapat saya jelaskan semoga bermanfaat Wassalamualaikum wr.wbJ