Binary Search Tree

Binary Search Tree

Binary search tree mempunyai ciri-ciri :

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 )

Aturan main Binary Search Tree :
Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya

Operasi-operasi yang dilakukan pada binary search tree meliputi : 
1. Operasi: Insertion BST
Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :
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 )
2. Operasi: Delete ( Remove )
akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

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)

3. Operasi: Search BST
dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.
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


ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data

sumber :
 https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
http://www.nblognlife.com/2014/12/binary-search-tree-bst-tree-lanjutan.html
http://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html