Binary Search Tree

BINARY SEARCH TREE (BST)

PENGERTIAN

Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent.

Operasi dasar pada Binary Search Tree :

1.  Find(x) : menemukan value x didalam BST (Search)
2.  Insert(x) : memasukan value baru x ke BST (Push)
3.  Remove(x) : menghapus key x dari BST (Delete)

Ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada Binary Search Tree :

• 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

Operasi : Search

Misalkan mencari value x

•  Memulai pencarian dari Root
•  Jika Root adalah value yang dicari, maka berhenti
•  Jika x lebih kecil dari Root, maka cari ke dalam rekursif tree sebelah kiri
•  Jika x lebih besar dari Root, maka cari ke dalam rekursif tree sebelah kanan

Operasi : Insertion

Memasukan value (data) baru kedalam BST dengan rekrusif

Misalkan 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 dipaling bawah biasa disebut Leaf atau daun)

Contoh Insertion :

Operasi : Delete (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)

Referensi :

https://socs.binus.ac.id/2017/05/10/implementasi-insert-pada-binary-search-tree-dengan-single-dan-double-pointer/

https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

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

Dibuat oleh :

Livia Leonita

2301905726

CB01