struktur data dan algoritma - aren.cs.ui.ac.idaren.cs.ui.ac.id/sda/resources/sda2010/11_bst.pdf ·...
TRANSCRIPT
Struktur Data dan Algoritma
Suryana Setiawan, Ruli Manurung & Ade Azurat(acknowledgments: Denny)
Fasilkom UI
SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P 2009/2010 – Ganjil – Minggu 9
Binary Search Tree
2SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Tujuan
Memahami sifat dari Binary Search Tree (BST)
Memahami operasi-operasi pada BST
Memahami kelebihan dan kekurangan dari
BST
3SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Outline
Properties of Binary Search Tree (BST)
Operation
Insert
find
remove
4SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Properties of Binary Search Tree
Untuk setiap node X pada tree, nilai elemen
pada subtree sebelah kiri selalu lebih kecil dari
elemen node X dan nilai elemen pada subtree
sebelah kanan selalu lebih besar dari elemen
node X.
Jadi object elemen harus comparable.
X
<X >X
5SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Binary Search Tree
936
5127
6SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
7
2
3
9
1 5
6
Binary Search Tree
7SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
3
2
1
3
1
2
2
1 3
1
3
2
1
2
3
Binary Search Tree
8SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Basic Operations
insert
findMin and findMax
remove
cetak terurut
9SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Print InOrderclass BinaryNode {
void printInOrder( )
{
if( left != null )
left.printInOrder( ); // Left
System.out.println( element ); // Node
if( right != null )
right.printInOrder( ); // Right
}
}
class BinaryTree {
public void printInOrder( )
{
if( root != null )root.printInOrder( );
}
}
10SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Insertion
Penyisipan sebuah elemen baru dalam binary
search tree, elemen tersebut pasti akan
menjadi leaf
10
2
3
15
1 5
6
12
14
11SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Insertion: algorithm
Menambah elemen X pada binary search tree:
mulai dari root.
Jika X lebih kecil dari root, maka X harus diletakkan
pada sub-tree sebelah kiri.
jika X lebih besar dari root, then X harus diletakkan
pada sub-tree sebelah kanan.
Ingat bahwa: sebuah sub tree adalah juga
sebuah tree. Maka, proses penambahan elemen
pada sub tree adalah sama dengan
penambahan pada seluruh tree. (melalui root
tadi)
Apa hubungannya?
permasalahan ini cocok diselesaikan secara rekursif.
12SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
BinaryNode insert(int x, BinaryNode t)
{
if (t == null) {
t = new BinaryNode (x, null, null);
} else if (x < t.element) {
t.left = insert (x, t.left);
} else if (x > t.element) {
t.right = insert (x, t.right);
} else {
throw new DuplicateItem(“exception”);
}
return t;
}
Insertion
13SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
BinaryNode findMin (BinaryNode t)
{
if (t == null) throw exception;
while (t.left != null) {
t = t.left;
}
return t;
}
FindMin
Mencari node yang memiliki nilai terkecil.
Algorithm:
ke kiri terus sampai buntu….:)
Code:
14SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
FindMax
Mencari node yang memiliki nilai terbesar
Algorithm?
Code?
15SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Find
Diberikan sebuah nilai yang harus dicari
dalam sebuah BST. Jika ada elemen tersebut,
return node tersebut. Jika tidak ada, return
null.
Algorithm?
Code?
7
2
3
9
1 5
6
16SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Remove
Kasus 1: jika node adalah leaf (tidak punya
anak), langsung saja dihapus.
Kasus 2: jika node punya satu anak: node
parent menjadikan anak dari node yang
dihapus (cucu) sebagian anaknya. (mem-by-
pass node yang dihapus).
Kasus 3: jika node punya dua anak…..
17SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
8
4
5
12
1 6
3
Remove
5
6
4
Kasus 1
Kasus 2
Kasus 3
18SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Removing 6
8
4
5
12
1 6
3
19SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
After 6 removed
8
5
12
1
3
4
6
20SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Remove (lanj.)
Bagaimana bila node punya dua anak?
1. Hapus isi node (tanpa mendelete node)
2. Gantikan posisinya dengan:
Succesor Inorder node terkecil dari sub tree
kanan, dilanjutkan dengan melakukan
removeMin di subtree kanan.
[Alternatif: dengan kaidah Predecesor Inorder,
2. Gantikan posisinya dengan:
Predecesor Inorder, node terbesar dari sub
tree kiri, dilanjutkan dengan melakukan
removeMax di subtree kiri.]
21SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
7
3
9
1 5
4
Removing 2 (Sucessor Inorder)
Cari node
berisi 2
22
22SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
7
9
1 5
4
Removing 2 (Sucessor Inorder)
2
Cari sucessor
Indorder
33
23SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
7
9
1 5
4
Removing 2 (Sucessor Inorder)
3
Gantikan
posisi yang
dihapus
24SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
After 2 deleted
7
3 9
1 5
4
Hapus node
ini
25SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Removing Root
7
2
3
12
1 5
4
10 14
9 11
9
26SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
removeMin
BinaryNode removeMin(BinaryNode t)
{
if (t == null) throw exception;
if (t.left != null) {
t.left = removeMin (t.left);
} else {
t = t.right;
}
return t;
}
27SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Remove
BinaryNode remove(int x, BinaryNode t) {
if (t == null) throw exception;
if (x < t.element) {
t.left = remove(x, t.left);
} else if (x > t.element) {
t.right = remove(x, t.right);
} else if (t.left != null && t.right != null) {
t.element = findMin(t.right).element;
t.right = removeMin(t.right);
} else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
28SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
removeMax
code?
29SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
SL
SR
X
k < SL + 1
SL
SR
X
k == SL + 1
SL
SR
X
k > SL + 1
Find k-th element
30SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Find k-th element
BinaryNode findKth(int k, BinaryNode t)
{
if (t == null) throw exception;
int leftSize = (t.left != null) ?
t.left.size : 0;
if (k <= leftSize ) {
return findKth (k, t.left);
} else if (k == leftSize + 1) {
return t;
} else {
return findKth ( k - leftSize - 1, t.right);
}
}
31SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Analysis
Running time:
insert?
Find min?
remove?
Find?
Worst case: O(n)
32SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Rangkuman
Binary Search Tree menjamin urutan elemen
pada tree.
Tiap node harus comparable
Semua operasi membutuhkan O(log n) -
average case, saat tree relatif balance.
Semua operasi membutuhkan O(n) - worst
case, tinggi dari tree sama dengan jumlah
node.
33SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9
Selanjutnya:
Sejauh ini struktur Binary Search terbentuk
dengan asumsi data cukup acak sehingga
seluruh bagian tree akan cukup terisi.
Benarkah asumsi tersebut?
Jika tidak benar, maka akan terbentuk tree
yang “tidak balance” yang berakibat tidak
tercapainya performance O(log n)
Solusi?
Dalam kuliah yad akan dibahas struktur
binary tree dengan kemampuan auto-
balancing AVL tree