Binary Search Tree

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. Binary Search Tree juga merupakan tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list
Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Aturan Dalam Membangun BST Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:

 1. Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.

 2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.

Pada dasarnya operasi dalam Binary Search Tree adalah sama dengan Binary Tree biasa, kecuali pada operasi insert, update dan delete.
• Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat.

• Update : Seperti pada Binary Tree biasa, namun jika update berpengaruh pada posisi node tersebut, sehingga menyebabkan Tree bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan cara melakukan rotasi supaya tetap menjadi Binary Search Tree kembali.

• Delete : Seperti halnya update, delete dalam binary search tree juga turut mempengaruhi struktur dari tree tersebut.

AVL Tree adalah binary search tree yang memiliki perbedaan tinggi/level antara subtree kiri dan subtree kanan maksimal adalah 1. AVL Tree muncul untuk menyeimbangkan binary search tree. Dengan AVL Tree waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Selain AVL Tree terdapat pula height balanced and Tree, yakni binary search tree yang memiliki perbedaan level antara subtree kiri dan subtree sehinga avl tree adalah height balanced 1 tree.