Binary Search Tree

Binary Search Tree atau biasanya disingkat menjadi BST itu adalah Struktur data Binary Tree yang mempunyai node dan yang berstruktur yaitu (Subtree kiri dan Subtree kanan harus binary tree):

-          Subtree sebelah kiri hanya terdiri dari node yang lebih kecil dari parents dan rootnya

-          Subtree sebelah kanan hanya terdiri dari node yang lebih besar dari parents dan rootnya

Binary Search Tree juga mempunyai kelebihan yaitu lebih cepat dama mencari, lebih cepat untuk sorting data dan juga lebih cepat dan lebih mudah untuk insert data dan delete data.

Berikut adalah contoh dari Binary search tree :

Didalam Binary Search Tree kita dapat melakukan Search, Insert dan juga delete:

Search:

Untuk search dalam Binary Search Tree, pertama-tama harus disamakan dengan root apabila nilainya sama dengan root maka return root-nya. Apabila nilai nya lebih besar daripada root maka cari di sebelah kanan dari Subtreenya, apabila lebih kecil daripada root-nya maka cari disebelah kiri dari rootnya.

Contoh codenya adalah sebagai berikut:

Insert:

Data baru yang di-insert selalu berada di leaf dalam binary tree. Sama seperti search, kita cari apabila datanya lebih kecil daripada root makacari secara recursive ke sebelah kiri dan apabila lebih besar maka kesebalah kanan. Setelah di search dan apabila sudah ketemu tempat yang memenuhi persyaratan maka data barunya menjadi leaf child dari nodenya.

Contoh codenya adalah sebagai berikut:

Delete:

Data yang ingin di-delete dapat berupa leaf, parent yang mempunyai satu child atau parent yang mempunyai dua child. Apabila yang ingin dihapus hanya leaf maka tinggal hapus saja, apabila ynag dihapus parent yang mempunyai satu child maka tinggal copy child-nya ke node dan hapus parentnya, dan apabila yang ingin dihapus parent yang mempunyai dua anak maka cari penerus dari parent tersebut setelah itu maka tinggal hapus dan replace dengan penerus dari parent yang sudah ditemukan

Contoh codenya adalah sebagai berikut: