BINARY SEARCH TREE TUJUAN UMUM Mahasiswa memahami binary search Tree
Tujuan Khusus – Bentuk Khusus Binary Tree – Rekursive pada Binary Tree – Tree Traversal – Operasi pada Binary Tree – Implementasi Binary Tree pada Array – Implementasi dengan double Linked List – Implementasi dengan Multi Linked List – Expression Tree
2. Binary Search Tree • Adalah binary tree dengan sifat bahwa 1. semua left child harus lebih kecil daripada right child dan parentnya. 2. Juga semua right child harus lebih besar dari left child serta parentnya. 3. Parent harus lebih besar dari left subtreedan harus lebih kecil dari right subtree. 4. Tidak boleh ada node yang mempunyai nilai yang sama, dengan kata lain tidak boleh terjadi duplikasi data.
Target Node Karena ketentuan di atas, maka Binary Seacrh tree dapat digunakan untuk tempat penyimpanan data secata terurut, sehingga pencarian data (searching) bisa lebih efisien. Untuk itu dapat ditentukan suatu target node yaitu node yang berisi data yang akan dicari.
Contoh Binary Search Tree Gita Edi
Bejo
Kemal
Farid
Halim
Silvi
Operasi-operasi pada binary search tree • Semua operasi pada binary search tree dapat digunakan pada Binary Search Tree, kecuali: – – –
•
Insert Update Delete
Perlu perubahan pada operasi Insert dan Delete sehingga urutan data di dalam tree dapat dipertahankan.
Insert(elemen_type e) Insert selalu dimuali dari Root node a. Bila tree kosong, maka node baru sebagai Root node b. Bila tidak kosong nilai e dibandingkan dengan nilai root c. Bila lebih kecil insert ke subtree kiri, bila lebih besat inser ke subtree kanan.
CONTOH Insert(12); Memasukkan sebuah node yang berisi angka 12. Karena tree masih kosong, maka secara otomatis node tersebutmenjadi root 12
Insert(15); Karena 15 lebih besar 12, maka sesuai dengan peraturan harus berada disebelah kanan parent (right child) 12 15
Insert(13); Karena 13 lebih besar 12, maka sesuai dengan peraturan harus berada disebelah kanan parent (right child), lalu dibandingkan lagi dengan 15. Karena lebih kecil maka 13 menempati left child dari 15. 12
15 13
Insert(9); Insert(5); Insert(11); Insert(20);
Delete( ) Semua proses delete akan dimulai dari binary search tree berikut: 20 10
50
5
12
4
40
65
6
Jika yang didelete adalah leaf node, maka tidak perlu perubahan posisi pada tree. Delete(4); 20
10 5
50 12
40
65
6
Jika yang didelete adalah node yang memiliki satu anak, maka anak tersebut menggantikan posisi parent. Delete(5);
20 10 5
50 12
40
65
6 20 10 6
50 12
40
65
Jika yang didelete adalah node yang memiliki dua anak, maka pengganti posisi parent dapat dipilih: a. Node terbesar dari subtree kiri atau b. Node terkecil dari subtree kanan Delete(20); 20 19 6
50 12
40
65
20 10 6
50 12
40
65
Dari subtree Kiri 12 10
50
6
40
65
Dari subtree Kanan 40 10 6
50 12
65
Update Seperti pada binary tree biasa, namun di sini akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan binary search tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary search tree. Pada dasarnya operasi ini merupakan gabungan dari operasi Delete dan Insert. Contoh: Update(34); Delete node yang ditunjuk oleh current kemudian insert 34.
LATIHAN: Bila tanda + menunjukkan Insert dan tanda – menunjukkan delete, gambarkan Binary search tree untuk data berikut: +45 +56 + 50 +30 -45 +54 +34 +55 50 +67 -54 2. Untuk Binary Search tree berikut, buat perintah-perintah dengan Find( ), Insert( ) dan Delete( ), untuk mengubah 50 menjadi 53. Gambar Binary Search tree yang terjadi . 20 10 6
50 12
40
65
AVL TREE • Kelemahan yang dialami oleh binary search tree adalah kemungkinan bentuk tree yang didapat adalah bentuk skewed (binary tree miring) sehingga pencarian menjadi sekuensial. • Untuk menghindari hal tersebut, digunakan AVL tree, di mana karakteristik dari tree tersebut adalah: Perbedaan tinggi/level antara subtree kiri dan subtree kanan maksimal adalah 1. Keseimbangan subtree kiri dan kanan, dijaga dengan suatu mekanisme rotasi, untuk itu perlu diterapkan beberapa kerentuan sebagai berikut: 1. Tanda Keseimbangan subtree: a. Node parent diberi tanda 0, bila ketinggian subtree kiri = subtree kanan. b. Node parent diberi tanda +, bila ketinggian subtree kiri < subtree kanan c. Node parent diberi tanda -, bila ketinggian subtree kiri > subtree kanan
20 10 5
4
0
0
50 16
6
+
14
-
40 30
+
0
65
46
61
54
-
0
76
63
2. Search Path Path dimana node baru akan melalui untuk sampai pada posisi insert. Contoh: Insert(17); 20
Search Path untuk data 17
10 5
50 12
40
65
3. Pivot Node Pivot Node adalah node yang: a. Berada di search-path b. Bertanda + atau – c. Paling dekat dengan node baru Pivot node merupakan sumbu putar, bila regenarasi tree diperlukan. 20
+
10 5
4
0
0 6
50 16
14
-
40 30
0
65
46
54
• • • •
+
61
0
76
63
Node 16 adalah pivot node, bila node baru = Node 65 adalah pivot node, bila node baru = Node 50 adalah pivot node, bila node baru = Node 20 adalah pivot node, bila node baru =
Operasi INSERT •
Kasus 1 Tidak terdapat pivot node, maka node baru langsung masuk tanpa harus melihat keseimbangan subtree Kasus 2 Terdapat pivot node, periksa keseimbangan subtree, bila node baru tidak menyebabkan perbedaan ketinggian subtree > 1 maka node dapat masuk tanpa regenarasi tree Keseimbangan subtree dilihat dari pivot node. Kasus 3 Terdapat pivot node, periksa keseimbangan subtree, bila node baru menyebabkan perbedaan ketinggian subtree > 1 maka node masuk dengan melakukan regenerasi tree.
•
•
Regenarasi Tree 1. Rotasi Tungggal(single Rotasion) –
2.
Rotasi Kiri atau Kanan
Rotasi Ganda( Double Rotation) – –
Rotasi Kiri kemudian Rotasi kanan atau Rotasi kanan kemudian rotasi kiri
Contoh Kasus 1 50
40
0
65
Insert dengan nilai node berapapun, langsung masuk, misalkan: Insert(54); 50
40
+
65
-
50
Contoh Kasus 2 50
40
+ 65
-
50
Insert(70), pivot node adalah node 65
50
40
+ 65
50
0 70
Contoh Kasus 3 Insert(72), pivot node adalah node 50
P 50 + 40
Menjadi anak Kiri
65 50
0
Menjadi Parent Menadi Anak Kanan
70 72
Gambar parent, anak kiri dan kanan 65
50
70
Tambahkan node 40 sebagai anak 50 dan node 72 sebagai anak 70. Diman posisi posisi 54? LATIHAN: 1. Lakukan operasi Insert untuk data: • • •
2.
3 12 2 10 56 15 13 10 20 30 40 50 60 70 75 65 55 45 35 25 15
Cari informasi tentang singkatan AVL, ia merupakan nama dua orang yang pertama kali membangun heightbalance tree.
Rotasi Ganda Insert(10);Insert(30) dan Insert(20); akan menghasilkan tree.
P 10+
Menjadi anak Kiri 30
Menjadi Parent
20
Menadi Anak Kanan Seandainya dilakukan rotasi tunggal menurut langkah-langkah yang telah dijelaskan pada pertemuan yang lalu, maka didapat hasil sebagai berikut: 30 10 20
Hasil tersebut tentu bukan yang diharapkan, oleh karena itu kasus seperti di atas harus diselesaikan dengan rotasi ganda.
P 10+ Rotasi Kedua
30
Rotasi Pertama
20
Hasil dari rotasi pertama:
P 10+
20 30
Hasil dari rotasi kedua: 20
10
30
Sesuai dengan yang diharapkan.
Contoh lain: Insert(53); 50
+
Rotasi Kedua 40
65
0 Rotasi Pertama
54
70
53
Hasil dari Rotasi Pertama: 50
Hasil dari Rotasi Kedua:
+
54
Rotasi Kedua 40
54 53
50 40
65
70
65 53
70
Rotasi Ganda Rotasi kiri kemudian Rotasi kanan. Insert(21) 29 10
0
5
4
50 16
6
-
14
0
0
40
65
22
Latihan: 1. Lakukan operasi Insert untuk data: a. b.
3, 12, 2, 10, 56, 8, 15, 18 10, 16, 14, 8, 9, 13, 12, 11, 15, 20, 18, 22, 17
Pada AVL tree.
OPERASI DELETE • Pada operasi delete, tidak ada pivot node, karena tidak ada node baru yang akan masuk. • Sebagai acuan bila operasi delete menyebabkan tree harus regenerasi, digunakan pemeriksaan secara berjenjang mulai dari anak node yang dihapus di mana node pengganti berada, dilanjutkan ke posisi node yang dihapus, kemudian terus naik hingga Root node. • Selama pemeriksanaan dapat terjadi beberapa rotasi baik rotasi tunggal maupun rotasi ganda, dengan demikian operasi delete merupakan operasi yang sangat kompleks, lebih sulit dari operasi insert.
