Materi pertemuan 4

Binary Search Tree

BST ( Binary Search Tree ) memiliki ciri-ciri :

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

Operasi dalam BST : 

1.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

2.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 )

contoh  

Kita ingin menambahkan value 35 kedalam BST yang sudah ada

yang berwarna hijau adalah root , setiap menginsert , mencari , atau delete selalu di mulai dari root.

dan new node berwarna orange yang memiliki value 35, kemudian kita cek dengan root(30), maka 30 .. 35 ?  karena 30 < 35 maka , node lebih besar dari root kemudian kita arahkan ke sub-tree yang berada di kanan dan kemudian cek ulang kembali

Sekarang kita cek 35 dengan 37 , maka 35 < 37 jadi kita arahkan ke bagian kiri dan kita cek kembali , karena di bagian kiri sudah ada value yaitu 32

kemudian kita cek 32 dengan 35 , ternyata 35 > 32 jadi kita masukan ke kanan , dan ternyata kita sudah menemukan tempat kosong untuk mengisi new node(35) jadi kita masukan 35 di sebelah kanan dari node(32)

3.Deletion

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

 Delete value(30) , value 30 adalah root dari BST , memiliki 2 anak sama seperti case sebelumnnya “Kiri , anak paling kanan atau kanan anak paling kiri”.

jadi kita bisa ambil ( 26 atau 31 ) untuk menggantikan root(30)

Joviandy Widyananda
CB01
LK01 
2301846225

referensi  

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