Dalam bidang ilmu komputer (computer science) binary search tree (BST) atau yang terkadang disebut juga sebagai sorted binary tree, merupakan semacam container struktur data, yang menyimpan informasi seperti bilangan atau nama yang ada di dalam memory. 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.
Binary search tree menempatkan key tersebut secara urut, yang memungkinkan pencarian dengan cara binary search. Binary tree terdiri dari node 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.
Sebagai contoh, bila terdapat nilai root sebesar 10 dan nilai yang akan dimasukkan ialah 7, maka data tersebut (yang bernilai 7) akan dimasukkan ke bagian kiri dari root.
Pada dasarnya ialah bahwa setiap node dapat diasumsikan sebagai binary tree itu sendiri. Setiap node memiliki 2 buah pointer, yakni di sisi kiri dan di kanan. Berdasarkan nilai yang dimasukkan, nilai tersebut akan ditempatkan di pointer sisi kanan jika nilai node tersebut lebih kecil dari yang dimasukkan, atau pointer kiri jika nilai pointer node lebih besar dari nilai yang akan dimasukkan.
Hal yang perlu untuk diketahui dari binary tree ialah bahwa hubungan antara node yang satu dengan yang lain dalam binary tree adalah satu-satu secara alami. Satu node hanya dapat diisi oleh satu nilai saja, selain itu bahwa satu buah node dapat menunjukkan paling banyak dua sub-node yang berbeda.
Keunggulan utama dari binary search tree jika dibandingkan struktur data lainnya ialah pada sorthing algorithm (pengurutan data) dan searching algorithm (pencarian data) secara lebih efisien.
Binary search tree mendukung tiga operasi utama yakni insertion of keys (memasukkan data), deletion of keys (menghapus data), dan pencarian data lookup. Setiap operasi tersebut membutuhkan data pembanding (comparator), sebuah subroutine yang melakukan proses komputasi keseluruhan urutan (linear order) dalam dua buah key. Data pembanding tersebut dapat didefinisikan secara langsung maupun tidak langsung, tergantung dari bahasa pemrograman yang digunakan dalam menyusun binary search tree tersebut. Contoh sederhana seperti a < b, dimana a dan b merupakan dua buah key dari dua node dalam suatu binary search tree.
Searching
Pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key dengan node root tersebut. Bila nilai root node sama seperti key yang dicari, maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.
Contoh pencarian secara recursive dilakukan sebagai berikut.
function Find-recursive(key, node):
if node = Null or node.key = key then
return node
else if key < node.key then
return Find-recursive(key, node.left)
else
return Find-recursive(key, node.right)
if node = Null or node.key = key then
return node
else if key < node.key then
return Find-recursive(key, node.left)
else
return Find-recursive(key, node.right)
Contoh pencarian secara recursive dilakukan sebagai berikut.
function Find(key, root):
current-node := root
while current-node is not Null do
if current-node.key = key then
return current-node
else if key < current-node.key then
current-node ← current-node.left
else
current-node ← current-node.right
return Null
current-node := root
while current-node is not Null do
if current-node.key = key then
return current-node
else if key < current-node.key then
current-node ← current-node.left
else
current-node ← current-node.right
return Null
Terdapat beberapa istilah yang digunakan untuk memudahkan merujuk pada suatu node. Node parent ialah suatu node dalam binary search tree yang memiliki child, atau terdapat satu subtree, children, bila memiliki dua subtree di sisi kanan dan kiri. Node child ialah node yang ada menjadi subtree dari node parent.
Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.
Deletion
Terdapat beberapa aturan dasar yang perlu diperhatikan dalam langkah menghapus suatu node, yakni.
- Bila node tersebut tidak memiliki child, node tersebut dapat langsung dihapus
- Bila node tersebut memiliki child, maka node (parent) tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent
- Bila node tersebut memiliki dua children, maka langkah pertama yang dilakukan ialah mengganti nilai node parent dengan salah satu child, hapus nilai node parent awal, secara recursive hapus nilai node child yang telah digunakan untuk mengganti nilai node parent sebelumnya, kemudian lakukan seperti pada kasus pertama atau kedua
Bila ada sesuatu yang belum jelas dan ingin tahu lebih dalam seputar project Arduino, pemrograman, dan elektronika, bisa bertanya pada bagian comment.