Binary Search Tree

Binary Search Tree

Sebuah Binary Search Tree atau BST singkatnya adalah suatu struktur data yang mendukung cepatnya pencarian, sorting atau peanataan beruntun dan juga masukan dan penghapusan data yang mudah. BST juga dikenal sebagai bentuk yang lebih berurutan dari Binary tree.

Pada BST terdapat juga hal-hal demikian:
  > Subtree kiri  dari suatu node biasanya hanya memiliki keys yang lebih sedikit dari pada key pada nodenya
  > Subtree kanan dari suatu node biasanya memiliki keys yang lebih banyak atau lebih besar dari pada key pada nodenya.
  > Subtree kiri dan kanan,masing-masing harus berbentuk BST dan tidak boleh ada node yang sama.

BST juga memiliki fungsi seperti, find, insert dan remove.

Pada BST biasanya juga disediakan dengan urutannya diantara keys agar dapat memudahkan operasi atau fungsi pencarian seperti mencari nilai minimum dan nilai maksimum. jika tidak ada urutan tersebut maka saat mencari akan dibutuhkan untuk setiap key dicari untuk menemukan kunci yang diperlukan.

Contoh dari BST =
>>

A. Find
Dengan fungsi ini pertama akan dibandingkan key dengan akar dari nodenya, jika key nya terdapat pada akar yang sesuai maka, return akarnya. Jika key nya lebih kecil dari key akarnya, maka kita bisa pindahkan ke subtree bagian kiri. Jika tidak berhasil maka pencarian akan dilemparkan ke bagian sebelah kanan.

B. Insert
>> Dimulai dari awal akarnya
>> Kedua, nilai yang akan ditambahkan akan dibandingkan dengan bagian kiri subtree, dan jika nialinya lebih besar dari bagian kiri subtree maka dimasukkan ke bagian kanan
>> Pengulangan akan terus terjadi hingga terdapat node kosong untuk dimasukkan nilai baru secara rekursif

C. Delete
>> Jika nilainya terdapat di akhir node atau leaf, maka bisa langsung di delete nodenya.
>> Jika key atau nilainya adalah sebuah node maka delete node tersebut dan sambungkan cabang yang berhubungan dengan bagian sebelumnya.
>> Jika key atau nilainya memiliki dua nak cabang maka cari anak paling kiri dari subtree kanan atau juga anak paling kanan dari subtree kiri untuk menggantikannya dan pengulangan terjadi secara rekursif hingga hasil telah didapatkan.