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
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 :
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:
Diperoleh dengan rumus sbb:
· 
Keterangan
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.
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
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
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
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
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
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
