DataStructure#5-2101639963-EnricoHermawan

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 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.

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.

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.

1. Bila node tersebut tidak memiliki child, node tersebut dapat langsung dihapus
2. Bila node tersebut memiliki child, maka node (parent) tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent
3. 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

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.