Memahami Pengertian Binary Search Tree

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 gosip ibarat bilangan atau nama yang ada di dalam memory. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, sanggup juga dipakai sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan memakai gosip 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 bab kiri dan bab kanan. Data disimpan sehabis root disimpan menurut 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 bab kiri dari root.
Pada dasarnya ialah bahwa setiap node sanggup diasumsikan sebagai binary tree itu sendiri. Setiap node mempunyai 2 buah pointer, yakni di sisi kiri dan di kanan. Berdasarkan nilai yang dimasukkan, nilai tersebut akan ditempatkan di pointer sisi kanan bila nilai node tersebut lebih kecil dari yang dimasukkan, atau pointer kiri bila 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 yaitu satu-satu secara alami. Satu node hanya sanggup diisi oleh satu nilai saja, selain itu bahwa satu buah node sanggup menawarkan paling banyak dua sub-node yang berbeda.
Keunggulan utama dari binary search tree bila 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 melaksanakan proses komputasi keseluruhan urutan (linear order) dalam dua buah key. Data pembanding tersebut sanggup didefinisikan secara eksklusif maupun tidak langsung, tergantung dari bahasa pemrograman yang dipakai dalam menyusun binary search tree tersebut. Contoh sederhana ibarat 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 sanggup dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melaksanakan 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 ibarat 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 sampai key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah menentukan 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)

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

Terdapat beberapa istilah yang dipakai untuk memudahkan merujuk pada suatu node. Node parent ialah suatu node dalam binary search tree yang mempunyai child, atau terdapat satu subtree, children, bila mempunyai 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 lalu dilakukan penambahan data key baru. Dengan kata lain dilakukan proses investigasi root dan secara recursive memasukkan suatu node gres di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau sanggup juga sama besar) dibandingkan dengan nilai dari root tersebut.

Deletion
Terdapat beberapa hukum dasar yang perlu diperhatikan dalam langkah menghapus suatu node, yakni.

1. Bila node tersebut tidak mempunyai child, node tersebut sanggup eksklusif dihapus
2. Bila node tersebut mempunyai child, maka node (parent) tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent
3. Bila node tersebut mempunyai 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 dipakai untuk mengganti nilai node parent sebelumnya, lalu lakukan ibarat pada kasus pertama atau kedua

Suatu node dengan children, lebih sulit untuk dihapus. Bila node child lebih besar dari node parent yang digantikan maka disebut in-order successor. Sebaliknya bila node child lebih kecil dari node parent yang digantikan, maka disebut in-order predecessor.

Bila ada sesuatu yang belum terang dan ingin tahu lebih dalam seputar project Arduino, pemrograman, dan elektronika, sanggup bertanya pada bab comment.
Sumber http://lang8088.blogspot.com/

Berlangganan Informasi Terbaru: