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.
·
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<m<n-1
·
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<E)(E,G)=3
·
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<Ni
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
