Binary Search Tree
Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.
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.
Lalu, 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
Oprasi: 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
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 )
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).
No comments:
Post a Comment