Pertemuan 5-Binary Search Tree-21010655475-Daniel Yuan Markus

Binary Search Tree

Apa perbedaan dari Binary Tree dengan Graph ?
- Binary Tree = Tree dimana mempunyai maximum anaknya 2 dan Tidak ada looping
- Graph = Memungkinkan pencarian node yang terus berulang (Looping)

Apa perbedaan dari Tree dan Binary Search Tree ?
- Tree = Tidak ada urutannya
- Binary Search Tree = Ada urutannya. Setiap child node sebelah kiri selalu lebih kecil nilainya            daripada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar              nilainya daripada root node (If value is less go left , If value is greater go right)

Contoh Binary Search Tree :



Contoh 2 : 
Jika terdapat data, x = {50,17,76,9,23,54,14,19,72,12,67}. Maka akan dibuat Binary Search Tree seperti dibawah ini



Binary Search Tree Operation
- find(x) / search(x) = Untuk mencari data
- insert(x) / push(x) = Untuk memasukkan data
- remove(x) / pop(x) = Untuk menghapus data


Contoh Insertion (insert) :
Jika kita ingin menambahkan angka 4 pada Binary Search Tree.
- Maka bandingkan angka 4 dengan angka 5 (Gambar 1). Karena angka 4 lebih kecil dari 5, maka go    to left child.
- Kemudian bandingkan angka 4 dengan angka 2 (Gambar 2). Karena angka 4 lebih besar dari 2,          maka go to right child.
-  Lalu bandingkan angka 4 dengan angka 3 (Gambar 3). Karena angka 4 lebih besar dari 3, maka go     to right child.
- Terakhir, Tempatkan angka 4 di sebelah kanan sebagai right child dari angka 3(Gambar 4)


Gambar 1

Gambar 2

Gambar 3

Gambar 4

Contoh Deletion (remove) :
Ketika kita  menghapus angka 18(Gambar 1), maka  angka 21 akan menggantikan tempat dari 18 & child dari 21 akan mengikuti dibawahnya  (Gambar 2).


Gambar 1


Gambar 2