Pertemuan 11

TREE

GENERAL TREE

TREE adalah suatu graph yang acyclic, simple, connected 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 :

• Satu root A -> Root(A) = V1
• Sisanya (V2, V3, ......, Vn) dipartisi menjadi Tm subtree ; di mana : 0 ≤ m ≤ n-1

CONTOH : TREE A

 KETERANGAN :

• Root (A) = B
• Leaf (A) = A, C, D, G, H
• B mempunyai 4 Subtree : A, C, I, D
• I mempunyai 2 Subtree  : E, F
• E mempunyai 1 Subtree : G
• F mempunyai 1 Subtree : H

LEVEL dari suatu vertex A dalam Tree A adalah LENGTH Path (P) (Root(A), A)
Dari gambar Tree A;

• Tentukan level A: 

- Length  (P) (Root(A), A)
- Length P(B,A) = (B,A) = 1 

• Tentukan level G:

- Length  (P) (Root(A), G)
- 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 ;

• High Tree A     = 3+1 = 4
• 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 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 :

- Similar.

- Informasi setiap vertex sama.

CONTOH : 

COMPLETE

Misalnya haeight dari binary tree T adalah K.

Binary Tree T disebut COMPLETE jika jumlah vertex dari binary tree T adalah :

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

 ALMOST COMPLETE

Misalnya height dari binary Tree T adalah K.

Binary Tree T disebut ALMOST COMPLETE jika :

• Pada level 0 hingga level ke-2 jumlah vertexnya adalah :

 pada level k-1 vertex-vertexnya terisi dari kiri ke kanan sebagai u, dimana 1 <= u <= 2 k-1

Contoh height dari binary tree T = 4. dan mis u = 5.

Gambar binary tree-nya :

4-2

∑ 2 i = (20 + 21 + 22) = 7

i      = 0

HEIGHT MIN dan HEIGHT MAX

Diperoleh dengan rumus sbb :

H_min = | log 2 (N+1) |  H_max =N

Keterangan :

- |    = fungsi celling dengan pembulatan ke atas.

- N   = jumlah vertex

Contoh :

Diberi 7 buah contoh vertex untuk membentuk suatu binary tree.

Hitung H min dan H max dari kemungkinan binary tree yang terbentuk. gambar binary tree-nya.

Jawab : H_min = | log 2 (7+1) |  H_max = N = 7

REPRESENTASI BINARY TREE

Contoh :

Algoritma untuk merubah General Tree menjadi Binary Tree

• Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang paling kiri.
• Rotasi 45 derajat sedemikan sehingga dibedakan subtree kiri dan kanan.

Contoh :

Algoritma untuk merubah Forest menjadi Binary Tree:

• Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri.
• Tree-tree yang lain dihitung sebagai satu level.

Contoh :

BINARY TREE TRANSVERSAL

Adalah proses menelusuri suatu Binary Tree sehingga demikian rupa setiap vertex dikunjungi hanya 1 kali.

3 aktivitas dalam Binary Tree Transversal :

• Visit the Root
• Transverse the left subtree
• Transverse the right subtree

Algoritma dalam Binary Tree Transversal

PRE-ORDER TRANSVERSAL

• Visit the Root
• Transverse the left subtree
• Transverse the right subtree

IN-ORDER TRANSVERSAL

• Transverse the left subtree
• Visit the Root
• Transverse the right subtree

POST-ORDER TRANSVERSAL

• Transverse the left subtree
• Transverse the right subtree
• Visit the root

CONTOH:
PRE-ORDER : V L R
-  + + * A B C D 

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 vertexnya (sebut Ri) ditempati oleh Ni untuk i = 1,2,3 . . . N.

Vertex-vertex dari Binary Tree tersebut diatur sedemikian rupa sehingga untuk setiap Ri harus memenuhi syarat sbb : 

- Jika Rj = left (Ri) maka Nj < Ni 

- Jika Rj = right (Ri) maka Nj > Ni

CONTOH :
Diketahui key dari 7 record (K, L, M, N, P, O, Q)
Binary Search Tree dari 7 key di atas dapat dibentuk :

Operasi-operasi pada Binary Search Tree

• Direct Search
• Sequential Search
• Insert Search
• Delete Search

DIRECT SEARH

Untuk mencari vertex k di 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 searh tree)
• Jika k < Ni maka subtree kiri dan Ri ditelusuri dan Ri = left. (Ri) kemudian kembali ke langkah 1.
• Jika k > Ni maka subtree kanan dan Ri ditelusuri dan Ri = right. (Ri) kemudian kembali ke langkah 1. 

CONTOH :
Carilah M dalam Binary Tree berikut secara Direct Search.
Berapa langkah atau perbandingan untuk mencari key M.
Bandingkan dengan rootnya, jika :

• Lebih besar maka cari ke kanan
• Lebih kecil maka cari ke kiri

SEQUENTIAL SEARCH
Untuk mencari vertex K dalam Binary Tree dengan root =Ri.
Algoritmanya menggunakan langkah-langkah :
IN-ORDER TRANSVERSAL (Left Visit Right)

CONTOH
Cari key M dalam Binary Tree berikut secar Sequential:

INSERT SEARCH

Prinsipnya sama dengan DIRECT.

4 langkah :

K > A

F > A

D > A

A = A

 

DELETE SEARCH

Dilihat dari link-listnya

BALANCED TREE

Suatu Binary Tree dimana untuk setiap Root Ri berlaku struktur subtree kiri = struktur subtree kanan.

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                              Bukan

                          Sama        1                                              Sama      2

Height balanced Tree belum tentu Balanced Tree tapi Balanced Tree sudah pasti Height Balanced Tree

Binary 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 + almost

Balance Tree = Almost Complete

                                   almost + balance              almost + balance

                                     TREE 1                     TREE 2               TREE 3

1. Tentukan ROOT masing-masing tree?
2. Tentukan LEAF masing-masing tree?
3. Rubahlah masing-masing general tree tersebut menjadi binary tree.
4. Tentukan HEIGHT dan WIGHT dari masing-masing tree?
5. Dari ketiga tree tersebut Bentuklah dalam 1 binary tree?
6. Dari hasil konversi tree 2 ke dalam binary tree carilah :
   - Pre-Order Transversal
   - In-Order Transversal
   - Post-Order Transversal