Binary Search Tree

March 17, 2020

Binary Search Tree

Binary Search Tree (BST)
merupakan sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent.

Ciri-ciri BST :

Setiap node mempunyai value dan tidak ada value yang double
value yang ada di kiri tree lebih kecil dari rootnya
value yang ada di kanan tree lebih besar dari rootnya
kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

Insert pada BST

Dimulai dari root
jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

deklarasi struct

function yang digunakan untuk membuat node baru

function untuk push(insert) -> single LL

function untuk push(insert) -> double LL

Delete pada BST

Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub tree anak kiri paling terakhir(leaf) (kanan,kiri)

pada tahap Delete pada BST diperlukan fungsi search yang digunakan untuk mencari sebuah node dengan nilai tertentu. Kemudian fungsi ini akan mengembalikan nilai berupa node yang ditemukan atau NULL jika nilai yang dicari tidak ditemukan.