Binary Search Tree

BINARY SEARCH TREE

• Binary Search Tree (BST) adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node.
• Aturan binary search tree :
1. Setiap node mempunyai value dan tidak ada value yang double
2. Value yang ada di kiri tree lebih kecil dari rootnya
3. Value yang ada di kanan tree lebih besar dari rootnya
4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

Sumber : https://www.programiz.com/dsa/binary-search-tree

• Operasi dalam binary search tree :
• 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

sumber : https://www.programiz.com/dsa/binary-search-tree

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

sumber : https://www.programiz.com/dsa/binary-search-tree

• Remove(x)  : menghapus key x dari BST ( Delete )
• Terdapat 3 case 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) ATAU dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri)

kita ingin delete node(37) memiliki 2 anak , jadi kita bisa ambil  (35 atau 42 ) untuk menggantikan value(37)