Algoritma dan Struktur Data
Binary Tree & Binary Search Tree (BST) Teknik Informatika Universitas Muhammadiyah Malang 2016
Outline • • • • •
Tree Binary tree Istilah pada tree Operasi dasar binary tree BST
Definisi • Tree adalah Kumpulan element yang saling terhubung secara hirarki (one to many). • Element pada tree disebut node.
http://people.cs.ksu.edu/~schmidt/300s05/Lectures/Week7b.html http://people.cs.ksu.edu/~schmidt/300s05/Lectures/Week7b.html
Aturan • Sebuah node hanya boleh memiliki satu induk/parent. Kecuali root, tidak memiliki induk/parent. • Setiap node dapat memiliki nol atau banyak cabang anak (one to many). • Node yang tidak memiliki cabang anak disebut daun
Contoh Tree
• Ada berapa node pada tree diatas? • Node manakah yang menjadi root? • Ada berapa jumlah node leaf/daun pada tree tersebut?
Contoh Tree
• Ada berapa node pada tree diatas? 18 • Node manakah yang menjadi root? Animal • Ada berapa jumlah node leaf/daun pada tree tersebut? 8
Istilah pada Tree
Latihan
Predesesor(F)? Succesor(B)? Ancestor (F)? Descendant (B)? Parent (I)? Child (C)?
Sibling (G)? Size? Height? Root? Leaf? Degree(C)?
Jawaban Predecesor (F) = A,B,C Succesor(B) = D,E,F,G,H,I Ancestor (F) = C,A Descendant (B) = D, E Parent (I) = H Child (C) = F,G,H
Sibling (G) = F,H Size = 9 Height = 4 Root = A Leaf = D,E,F,G,I Degree (C) = 3
Test Pemahaman 1. 2. 3. 4. 5.
Apa itu leaf/daun? Apa itu root? Apa itu level pada tree? Apa itu subtree? Apa itu binary tree?
Binary Tree • Binary tree = pohon biner • Tiap node-nya memiliki maksimal 2 cabang
Contoh tree
http://people.cs.ksu.edu/~schmidt/300s05/Lectures/Week7b.html
Contoh binary tree R
S
X
T
U
Y
Z
V
W
Contoh Binary Tree
Latihan • Cari sebuah contoh kasus yang dapat direpresentasikan dengan tree! • Gambarkan bentuk tree dari kasus tersebut sampai level 3! • Dari tree yang dibuat tsb, tentukan root, daun, height, size, predesesor, ancestor, descendant, successor, dll. • Tentukan apakah tree yang terbentuk termasuk binary tree atau bukan?
Representasi Binary Tree • Binary tree dapat direpresentasikan dengan menggunakan array maupun linked list.
Representasi Binary Tree Representasi binary tree menggunakan array (root pada index 0) :
H
D
K
B
F
J
L
A
C
E
G
I
0
1
2
3
4
5
6
7
8
9
10
11
Latihan Representasikan dengan array! a
b
d h
c
f
e i
j
g
Jawaban
tree[]
a b c d e f g h i 0
j 11
Linkedlist Representation root
A B
C F
D
G
E J H leftChild
I element
rightChild
Akses Elemen • Posisi node dapat ditentukan berdasarkan rumus berikut : • Asumsi root dimulai dari index 0 : – Anak kiri dari node i berada pada indeks : 2*i+1 – Anak kanan dari node i berada pada indeks : 2*i+2
• Asumsi root dimulai dari index 1 : – Anak kiri dari node i berada pada indeks : 2*i – Anak kanan dari node i berada pada indeks : 2*i+1 Struktur Data - Tree
21
Binary Tree Traversal • Teknik Penelusuran seluruh node pada binary tree. • Ada 4 metode : – Preorder – Inorder – Postorder – Level order
PreOrder Traversal Algoritma Preorder traversal : 1. Cetak data pada root 2. Secara rekursif mencetak seluruh data pada subpohon kiri 3. Secara rekursif mencetak seluruh data pada subpohon kanan
Preorder Example (visit = print) a b
c a b c
Preorder Example (visit = print) a b f
e
d g
c
h
i
j
Preorder Example (visit = print) a b f
e
d g
c
h
i a b d g h e i c f j
j
Preorder Of Expression Tree /
+
*
e + a
b
c
d
/ * + a b - c d + e f Gives prefix form of expression!
f
Inorder Traversal Algoritma Inorder traversal : 1.Secara rekursif mencetak seluruh data pada subpohon kiri 2.Cetak data pada root 3.Secara rekursif mencetak seluruh data pada subpohon kanan
Inorder Example (visit = print) a
b
c b a c
Inorder Example (visit = print) a b f
e
d g
c
h
i
j
Inorder Example (visit = print) a b f
e
d g
c
h
i
g d h b e i a f j c
j
Postorder Traversal Algoritma Postorder traversal : 1.Secara rekursif mencetak seluruh data pada subpohon kiri 2.Secara rekursif mencetak seluruh data pada subpohon kanan 3.Cetak data pada root
Postorder Example (visit = print) a
b
c b c a
Postorder Example (visit = print) a b
f
e
d g
c
h
i
j
Postorder Example (visit = print) a b
f
e
d g
c
h
i
g h d i e b j f c a
j
Postorder Of Expression Tree /
+
* e + a
b
c
d
a b + c d - * e f + /
Gives postfix form of expression!
f
BINARY SEARCH TREE (BST)
Binary Search Tree (BST) • Disebut juga Ordered Binary tree • yaitu binary tree yang seluruh node-nya terurut. • Aturan : data pada subtree kiri lebih kecil dari data pada subtree kanan.
Contoh BST Root = 20
20
10
6
2
40
15
8
30
25
Penambahan BST Aturan minMax: • Node yang bernilai lebih kecil dari root diletakkan pada subtree sebelah kiri. • Node yang bernilai lebih besar diletakkan pada subtree sebelah kanan. • Jika ada nilai yang sama maka node tersebut di-overwrite.
Latihan • Buatlah sebuah Binary Search Tree berdasarkan proses-proses berikut : insert 17, insert 8, insert 32, insert 6, insert 10, insert 21, insert 45, insert 1, insert 7, insert 9, insert 26, insert 37, insert 50.
Penghapusan BST Ada 3 kasus : Node adalah leaf/daun. Node memiliki degree 1. Node memiliki degree 2.
Penghapusan Node Daun (Node 7) 20
10
6
2
40
15
8
30
18
25
35
7
Remove a leaf element. key = 7
Penhapusan Node Daun (Node 35) 20
10
6
2
40
15
8
30
18
25
35
7
Remove a leaf element. key = 35
Penghapusan Node Ber-degree 1 (Node 40) 20
10
6
2
40
15
8
30
18
25
35
7
Remove from a degree 1 node. key = 40
Penghapusan Node Ber-degree 1 (Node 15) 20
10
6
2
40
15
8
30
18
25
35
7
Remove from a degree 1 node. key = 15
Aturan penghapusan node degree 2 • Sebagai pengganti node yang dihapus dengan degree 2. aturannya sbb : ambil node paling besar dari subtree kiri atau ambil node paling kecil dari subtree kanan.
Penghapusan Node Ber-degree 2 (Node 10) 20
10
6
2
40
15
8
30
18
25
35
7
Remove from a degree 2 node. key = 10
Remove From A Degree 2 Node 20
10
6
2
40
15
8
30
18
25
35
7
Replace with largest key in left subtree (or smallest in right subtree).
Penghapusan Node Ber-degree 2 20
10
6
2
40
15
8
30
18
25
35
7
Replace with largest key in left subtree (or smallest in right subtree).
Penghapusan Node Ber-degree 2 20
8
6
2
40
15
8
30
18
25
35
7
Replace with largest key in left subtree (or smallest in right subtree).
Latihan 20
10
6
2
40
15
8
30
18
25
35
7
Remove from a degree 2 node. key = 20
Penghapusan Node Ber-degree 2 20
10
6
2
40
15
8
30
18
25
35
7
Replace with largest in left subtree.
Penghapusan Node Ber-degree 2 20
10
6
2
40
15
8
30
18
25
35
7
Replace with largest in left subtree.
Penghapusan Node Ber-degree 2 18
10
6
2
40
15
8
30
18
25
35
7
Replace with largest in left subtree.
Hasil Akhir 18
10
6
2
15
8
7
40
30
25
35
Implementasi Binary Search Tree
Operasi Binary Search Tree • Operasi-operasi yang dilakukan pada binary search tree meliputi : 1. Penambahan node 2. Penghapusan node 3. Pencarian node
Contoh program • Penghapusan: Node2P remove(int x, Node2P t) { if (t == null) t=null; if (x < t.data) { t.previous = remove(x, t.previous); } else if (x > t.data) { t.next = remove(x, t.next); } else if (t.previous != null && t.next != null) { t.data = findMin(t.next).data; t.next = removeMin(t.next); } else { t = (t.previous != null) ? t.previous : t.next; } return t; }
Contoh program • Penghapusan node terkecil : Node2P removeMin(Node2P t) { if (t == null) t=null; if (t.previous != null) { t.previous = removeMin (t.previous); } else { t = t.next; } return t; }
Contoh program Pencarian Node terkecil : Node2P findMin (Node2P t) { if (t == null) t=null; while (t.previous != null) { t = t.previous; } return t; }
Pustaka • Sartaj Sahni , “Data Structures & Algorithms”, Presentation L20-24. • Mitchell Waite, “Data Structures & Algorithms in Java”, SAMS, 2001
