Binary Search Tree

Binary Search Tree (BST)

Binary Search Tree adalah 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.

Operasi Dasar

Search

Find(x)     : find value x didalam BST ( Search )

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

Insertion

Insert(x)   : memasukan value baru x ke BST ( Push )

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

Contoh:

Delete

Remove(x)  : menghapus key x dari BST ( Delete )

• 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)

Contoh:

Referensi:

https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/