Struktur Data dan Algoritma Binary Search Tree Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny)
Fasilkom UI
SUR – 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
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
2
Outline
Properties of Binary Search Tree (BST) Operation
Insert find remove
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
3
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 SUR – HMM – AA
>X
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
4
Binary Search Tree 7
2 6
SUR – HMM – AA
1
3
5
9
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
5
Binary Search Tree 7 9
2 1
5
3
SUR – HMM – AA
6
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
6
Binary Search Tree 3 2
3
1
1 2
1
3
2
1
3 2
2 1 SUR – HMM – AA
3
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
7
Basic Operations
insert findMin and findMax remove cetak terurut
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
8
Print InOrder class BinaryNode { void printInOrder( ) { if( left != null ) left.printInOrder( ); System.out.println( element ); if( right != null ) right.printInOrder( ); } }
// Left // Node // Right
class BinaryTree { public void printInOrder( ) { if( root != null ) root.printInOrder( ); } }
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
9
Insertion
Penyisipan sebuah elemen baru dalam binary search tree, elemen tersebut pasti akan menjadi leaf 10 15
2 1
3 SUR – HMM – AA
12
5
6
Fasilkom UI – IKI20100/IKI80110P
14 2009/2010 – Ganjil – Minggu 9
10
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.
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
11
Insertion 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; }
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
12
FindMin
Mencari node yang memiliki nilai terkecil. Algorithm:
ke kiri terus sampai buntu….:)
Code:
BinaryNode findMin (BinaryNode t) { if (t == null) throw exception; while (t.left != null) { t = t.left; } return t; } SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
13
FindMax
Mencari node yang memiliki nilai terbesar Algorithm? Code?
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
14
Find
Diberikan sebuah nilai yang harus dicari dalam sebuah BST. Jika ada elemen tersebut, return node tersebut. Jika tidak ada, return null. 7 Algorithm? Code? 9 2 1
5
3 SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
6 2009/2010 – Ganjil – Minggu 9
15
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-bypass node yang dihapus). Kasus 3: jika node punya dua anak…..
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
16
Remove 8
12
4
Kasus 3
6
1 3
SUR – HMM – AA
5
Kasus 2
Kasus 1
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
17
Removing 6 8
12
4
6
1 3
SUR – HMM – AA
5
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
18
After 6 removed 8
12
4
6
1 3
SUR – HMM – AA
5
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
19
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.]
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
20
Removing 2 (Sucessor Inorder) Cari node berisi 2
7 9
2
1
5 3 4
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
21
Removing 2 (Sucessor Inorder) 2
7 9
1
5
Cari sucessor Indorder
3 4
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
22
Removing 2 (Sucessor Inorder) Gantikan posisi yang dihapus
7 9
1
5 3 4
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
23
After 2 deleted 7 9
3 1
5 Hapus node ini
4
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
24
Removing Root 7 9 12
2 1
10
5 3
9
14 11
4
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
25
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;
}
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
26
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; } SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
27
removeMax
code?
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
28
Find k-th element
X
X
SR SL
k < SL + 1
SUR – HMM – AA
X
SR SL
k == SL + 1
Fasilkom UI – IKI20100/IKI80110P
SR SL
k > SL + 1
2009/2010 – Ganjil – Minggu 9
29
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); } } SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
30
Analysis
Running time:
insert? Find min? remove? Find?
Worst case: O(n)
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
31
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.
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
32
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 autobalancing AVL tree
SUR – HMM – AA
Fasilkom UI – IKI20100/IKI80110P
2009/2010 – Ganjil – Minggu 9
33