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  

Graph Berarah dan Tidak Berarah

Assalamualaikum wr.wb 

Hai teman-teman, kali ini saya akan membahas tentang GRAPH. Apa sih Graph itu ? .

GRAPH adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E). Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Dimana

            G = Graph

            V = Simpul atau Vertex , atau Node, atau Titik

            E = Busur atau Edge , atau Arc

Graph dibagi menjadi dua yaitu :

DIREKTED (Berarah)

Urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. Urutan simpul mempunyai arti. Misal busur RI adalah e1 sedangkan busur IR adalah e8.

Keterangan Simpul atau Node:

                      R = v1            

                      I   = v2

                      D  = v3

                      H  = v4

                      O = v5

            Keterangan Busur :

                      R1  = e1

                      IR  = e8

                      RO = e2

                      OH = e6

                      OD = e5

                      DH = e7

                      ID  =  e3

                      IH  =  e4

                      DI  = e9

                      DO = e10

           

UNDIREKTED (Tidak Berarah )

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur MU atau UM.

Keterangan Busur : Busur e1 dapat disebut Busur  MU atau UM

                                Busur e2 dapat disebut Busur  MA atau AM

                                Busur e3 dapat disebut Busur  UN atau NU

                                Busur e4 dapat disebut Busur  UF atau FU

                                Busur e5 dapat disebut Busur  AN atau NA
                                Busur e6 dapat disebut Busur  AF atau FA

                                Busur e7 dapat disebut Busur  NF atau FN      

Secara umum terdapat dua macam representasi dari struktur data graf yang dapat diimplementasi. 

- Pertama, disebut Adjacency List( diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur data yang mengandung semua simpul yang saling berhubungan). 

- Kedua adalah representasi berupa Adjacency Matrix dimana baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan sebuah entri di dalam  menyatakan apakah terdapat sisi di antara kedua simpul tersebut.

* Adjacency List

Dalam teori graf, adjacency list merupakan bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul yang saling terkait tersebut..

Graf pada gambar diatas dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency list dapat digambarkan melalui tabel di bawah ini.

Tabel 1. Representasi Adjacency List 

Vertex	Adjacency	Array of Adjacent
A	Adjacent to	B,c
B	Adjacent to	A,c
C	Adjacent to	A,b

Salah satu kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul.

Adjacency Matrix
Adjacency Matrix merupakan representasi matriks yang menyatakan hubungan antar simpul dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar simpul.

Gambar diatas merupakan adjacency matrix yang berkorelasi dengan graf tak berarah. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6. Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit.

Sekian penjelasan dari saya , mohon maaf jika ada kesalahan J .Wassalamualaikum wr.wb