Data Structures Pertemuan 5
BST (Binary Search Tree)
Di dalam BST, data akan lebih mudah untuk dicari karena semua data telah terurut, berbeda dengan binary tree.
Terdapat 3 operasi di dalam BST yaitu:
- Insert : push data
- Search : mencari data
- Delete : pop data
INSERT
Dalam pushing data, terdapat ketentuan yaitu
edge sebelah kiri untuk angka yang lebih kecil dari induknya
edge sebelah kanan untuk angka yang lebih besardari induknya
contoh push angka: 5,9,2,3,4.
SEARCH
Memiliki konsep yang sama dengan pop
Apabila data yang dicari lebih besar, maka lakukan pemcarian pada edge sebelah kanan dari induknya
Namun sebaliknya bila data yang dicari kebil kecil, lakukan pencarian pada edge sebelah kiri dari induknya.
Contoh:
search 4
DELETE
Pada BST delete dilakukan dengan:
Apabila node yang akan dihapus tidak memiliki anak sama sekali maka node tersebut dapat secara langsung dihilangkan
Bila node yang dihapus merupakan suatu bagian dari sebelah kiri root
Bila memiliki 2 anak maka tempatkan anak yang lebih kecil untuk menggantikan yang telah dihapus
Bila memiliki 1 anak maka child dari node tersebut digunakan untuk mengganikan node yang telah dihapus
Bila node yang dihapus merupakan bagian dari sebelah kanan root
Bila memiliki 2 anak maka tempatkan anak yang lebih besar untuk menggantikan node yang telah dihapus
Bila memiliki 1 anak maka child dari node tersebut digunakan untuk mengganikan node yang telah dihapus
