Binary Search Tree

Binary Search Tree atau disingkat BST adalah Sebuah algoritma yang diterapkan dalam Binary Tree yang fungsinya mempercepat pencarian. BST memiliki kecepatan pencarian yang sangat cepat yaitu (O)log n. Untuk dapat menerapkan BST , maka kita harus memisahkan dulu mulai dari root , hingga children childrennya , children sebelah kiri harus dibuat lebih kecil dari parentnya , sedangaan sebelah kanan lebih besar dari parentnya , atau sebaliknya , jika sudah ter insert seperti itu barulah BST dapat mencari dengan akurat dan sangat cepat.

Operasi operasi BST :
– Find (x)
– Insert(x)
– Delete(x)

• Find / Searching pada BST

Operasi Find dalam BST inilah yang dapat membuat BST sangat terkenal dan masih banyak dipakai sampai sekarang. Dalam operasi find ini BST merupakan algoritma pencarian yang sangat cepat , bahkan untuk search 10.000.000 data , BST masih dapat menanganinya dengan mudah. Berbeda dengan linear search yang harus mencari 1 per 1 data sehingga search linear sangat lambat dibandingkan BST.
Dalam pencarian menggunakan BST , data sebelah kiri dan kanan mempunyai sifat yang bertolak belakang yaitu lebih kecil dan lebih besar. Untuk ilustrasi search , jika data yang di search adalah lebih kecil dari root , maka dia akan langsung bergerak kearah data yang lebih kecil , dan langsung mengabaikan siblings nya(baca di rangkuman 4 untuk siblings) , dan begitu juga selanjutnya sampai datanya ditemukan / tidak ada. Jadi BST akan banyak mengabaikan data data yang tidak perlu untuk ditelusuri karena sudah diketahui data yang dicari tidak aka nada disana sehingga BST sangatlah menang jauh dibandingkan Linear Search.

• Insertion

Insertion dalam BST juga merupakan hal yang sangat penting , namun disinilah dapat menjadi kelemahan BST.

BST perlu algoritma insert yang benar , dan cara pengaplikasiannya biasanya menggunakan rekursif. Para programmer pemula pasti menemukan banyak kesulitan untuk membuat code rekursif , disinilah dapat terjadi banyak kesalahan.

Untuk menginsert suatu nilai baru kedalam BST , diperlukan sebuah kondisi, missal : jika data lebih kecil maka akan mengecek children sebelah kiri , jika data lebih besar maka akan mengecek children sebelah kanan. Pengecekan akan dilakukan terus menerus hingga menemukan node kosong, di node kosong itu , insert dalam BST membuat leaf baru disebelah kiri parentnya jika data lebih kecil , atau disebelah kanan parentnya jika data lebih besar.

• Deletion

Dalam BST , untuk mendelete suatu data , ada beberapa kondisi yang harus di cek:

• Jika node yang akan dihapus merupakan leaf / tidak mempunyai children
• Jika node yang akan dihapus mempunyai hanya 1 children
• Jika node yang akan dihapus mempunyai 2 children.

——————————————————————————–

• Jika node yang ingin dihapus merupakan leaf maka leaf dapat langsung dihapus.
• Jika node yang ingin dihapus mempunyai 1 children , maka langsung sambungkan children dengan parent dari node itu.
• Jika node yang akan dihapus mempunyai 2 children , maka carilah node terbesar pada left child , atau node terkecil pada right child , lalu replace dengan node yang akan dihapus.

skyconnectiva.com binus.ac.id