Jumat, 13 Februari 2015

TREE

0
TREE

Definisi
·         Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data dimana setiap simpul memiliki anak
·        Secara khusus anaknya dinamakan kiri dan kanan.



GENERAL TREE
·         TREE adalah suatu graphyang acyclic, simple, conneted yang tidak mengandung loop.
·         ROOT  Tree A ; suatu vertex dengan derajat masuk=0
·         LEAF Tree A ; suatu vertex dengan derajat keluar=0
·         Tree A atas vertex-vertex : V1,V2,V3,.....Vn harus mempunyai :
o   Satu root A – Root (A) = V1
o   Sisanya (V2,V3,......Vn) dipartisi menjadi Tm subtree; dimana  0
·         Contoh TREE A
·         Keterangan
o   Root  (A) = B
o   Leaf (A)= A,C,D,G,H
o   B mempunyai 4 subtree : A,C,I,D
o   I mempunyai 2 subtree : E,F
o   E mempunyai 1 subtree : G
o   F mempunyai 1 subtree : H



 

·         LEVEL dari suatu vertex A dalam Tree A adalah LENGTH path (P) (Root (A),A)
·         Dari gambar tree A:
o   Tentukan level A: 1. Length P(Root(A),A)
                                    2. Length P(B,A)=(B,A)=1
o   Tentukan level G : 1. Length P(root(A),G)
                                 2. Length p(B,G = (B,I)(I
·         HIGH dari suatu tree A adalah level tertinggi ditambah 1
·         WEIGHT dari suatu tree A adalah jumlah leaf dalam tree A
·         Contoh dari Tree A;  1.        High Tree A= 3+1= 4
                                     2.           Weight Tree A = 5 (A,C,D,G,H)
FOREST
·         Forest merupakan koleksi dari tree-tree



BINARY TREE
·         

Binary tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max=2

















SIMILAR dalam 2 BINARY TREE

·         Dua binary tree dikatakan Similar, jika struktur dari kedua Binary Tree sama







EKIVALEN dalam 2 BINARY TREE
·         Dua Binary Tree dikatakan Ekivalen jika, 1. Similar
2. Informasi setiap vertex sama
·         Contoh








COMPLETE
·         Misalnya height dari binary tree T adalah k.
·         Binary Tree T disebut COMPLETE jika jumlah verteks dari binary tree T adalah



Contoh height dari binary tree T=4. Gambar binary tree-nya :










 
 ALMOST COMPLETE
·         Misalnya heigt dari binary tree T adalah k
·         Binary Tree T disebut ALMOST COMPLETE jika:
o   
Pada level 0 hingga level ke-2, jumlah verteksnya adalah :

 
 o   Pada level ke-1 verteks-verteksnya terisi dari kiri ke kanan sebagai u,
 dimana 1<=u<=2 k-1
·         Contoh height dan binary tree T=4 dan mis u= 5
·         Gambar binary tree-nya:

 
 
HEIGHT MIN dan HEIGHT MAX
·         Diperoleh dengan rumus  sbb:


·         Keterangan


·         
Contoh : Diberi 7 buah vertex untuk membentuk suatu binary tree.Hitung H min dan H max dari kemungkinan binary tree yang terbentuk. Gambar binary treenya.
REPRESENTASI BINARY TREE
·         Contoh :

 

 






·        Algoritma untuk merubah General Tree menjadi Binary tree:

o   Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri
o   Rotasi 45o sedemikian sehingga dibedakan subtree kiri dan kanan
o   Contoh







 
 
·         Algoritma untuk merubah Forest menjadi Binary tree:
o   Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri
o   Tree-tree yang lain dihitung sebagai satu level
o   





Contoh






BINARY TREE TRANSVERSAL
·         Adalah proses menelusuri suatu Binary Tree sehingga sedemikian rupa setiap vertex dikunjungi hanya 1 kali
·         3 aktivitas dalam Binary Tree Transversal:
o   Visit the Root
o   Transverse the left subtree
o   Transverse the right subtree
ALGORITMA dalam BINARY TREE TRANSVERSAL
·         PRE_ORDER TRANSVERSAL
o   Visit the root
o   Tranverse the left subtree
o   Tranverse the right subtree
·         IN-ORDER TRANVERSAL
o   Tranverse the left subtree
o   Visit the root
o   Transverse the right subtree
·         POST-ORDER TRANVERSAL
o   Tranverse the left subtree
o   Tranverse the right subtree
o   Visit the Root
·         Contoh PRE-ORDER : V L R  ( - + + * A B C D)

 

·         Contoh IN-ORDER : L V R (- A * B  + C + D)

 
 
     POST-ORDER : L R V (- A B * C + D +)

 
 


BINARY SEARCH TREE
·         Suatu Binary Search Tree dari himpunan N record (N1,N2,N3....Nn) adalah suatu binary tree yang setiap vertex-nya (sebut Ri) ditempati oleh Ni untuk i=1,2,3....N
·         Vertex-vertex dari Binary Tree tsb. Diatur sedemikian rupa sehingga untuk Ri harus memenuhi syarat sbb:  1. Jika Rj= left (Ri) maka Nj
                                          2. Jika Rj= right (Ri) maka Nj>Ni
·         Contoh : Diketahui key dari 7 record (K, M, L, N, P, O, Q)





                Binary Search Tree dari 7 key diatas dapat dibentuk :





OPERASI-OPERASI pada BINARY SEARCH TREE
·         Direct Search
o   Untuk mencari vertx k dalam binary search tree dengan root=Ri, algoritmanya adalah sbb:
§  Jika tree kosong maka search tidak sukses (k tidak ada dalam binary search tree)
§  Jika k = Ni maka search sukses (k ada dalam binary search tree)
§  Jika k< Ni maka subtree kiri dari Ri ditelusuri dan Ri = left. (Ri) kemudian kembali ke langkah 1
§  Jika k > Ni maka subtree kanan dari Ri ditelusuri dan Ri= right . (Ri) kembali ke langkah 1
o   Contoh :  1. Carilah Key M dalam Binary Tree berikut secara Direct Search
                 2. Berapa langkah/perbandingan yang dibutuhkan untuk mencari key M
§  Bandingkan dengan rootnya, jika :
ü  Lebih besar maka cari ke kanan
ü  
Lebih kecil maka cari ke kiri


 

·         Sequential Search
o   Untuk mencari vertex K dalan binary search tree dengan Root=Ri
o   Algoritmanya menggunakan langkah-langkah: IN-ORDER TRANSVERSAL ( L V R)
o   Contoh :
 







·         Insert Search
o   Prinsip sama dengan DIRECT
o   4 langkah : K > A
                     F > A
                     D > A
                     A= A




·         Delete Search
o   Dilihat dari link – list nya
·         BALANCED TREE
o   Suatu Binary Tree dimana untuk setiap Root Ri berlaku struktur subtree kiri = struktur subtree kanan.
o   Contoh






HEIGHT BALANCED TREE
·         Suatu Tree dimana untuk setiap Root Ri berlaku height dari subtree kanan dan height dari subtree kiri beda paling banyak satu
·         
Contoh : Height Balanced Tree



·    





     Height Balanced tree belum tentu Balanced Tree tapi Balanced Tree sudah pasti height balanced tree
·         
Binary tree yang complete = balance tree






·        Balance tree belum tentu binary tree complete

 
·         Height Balance tree belum tentu Binary Tree Complete

 

 



·         Height Balance Tree belum tentu Almost Complete

 
 



·         Balance tree = Almost  Complete



 
Read More