Binary Search Tree

• Pengertian :
• Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut:Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.
• Contoh penggunaan :

• Operasi dasar dalam BTS :
• 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 :
• 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 )
• Remove :
• 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)