PERTEMUAN KELIMA BINARY SEARCH TREE

BINARY SEARCH TREE

Apakah itu Binary Search Tree? Binary Search Tree atau BST adalah Binary Tree dimana Tree tersebut dibuat sedemikian rupa sehingga dapat mempermudah pencarian data yang terdapat dalam sebuah Tree. Sesuai dengan post sebelumnya BST hanya memiliki 2 orang "anak" yang biasa disebut sebagai left dan right sesuai dengan posisi masing-masing.

Didalam Binary Search Tree terdapat 3 fungsi yang berkaitan dengan pencarian yang dapat dilakukan yaitu Find/Search, Insertion, dan Delete. Masing-masing fungsi ini memiliki fungsi sesuai dengan namanya Find untuk mencari, Insertion untuk memasukan data baru kedalam tree, dan Delete untuk menghapus data yang sudah ada didalam sebuah Tree. Fungsi Delete ini biasanya sangat terkait dengan fungsi Find/Search karena didalam pemrograman jika kita ingin menghapus suatu data kita harus meminta user untuk memilih data yang ingin dihapus, tapi bagaimana cara mencari data tersebut dan bagaimana jika data tersebut ternyata tidak ada? Disinilah fungsi Find/Search sangat berpengaruh. Fungsi search akan mencari input dari user dan jika tidak ada yang sesuai maka user akan diberitahu bahwa data tersebut tidak ada dan jika ada data tersebut akan dihapus dari Tree.

Berikut adalah cara kerja atau logika dari 3 fungsi diatas:

1.) Find/Search

1. Data dicari dari atas atau dari Root
2. Jika "parent" adalah data yang dicari maka isi dari "parent" akan di return
3. Jika data yang dimasukan lebih kecil dari Root maka data akan dicari ke "left" dari data diatasnya lalu jika benar maka akan di return
4. Jika data yang dimasukan lebih kecil dari "left maka data akan dicari ke "right" dari data diatasnya lalu jika benar maka akan di return
5. Langkah 2,3, dan 4 akan terus diulangi sampai data yang diinput user ditemukan atau semua data sudah di search

2.) Insertion

1. Cek apakah ada node root. Jika belum ada maka node yang akan di insert menjadi root. Apabila ada, bandingkan data yang akan dimasukkan dengan node tersebut.
2. Jika data yang akan di- insert lebih besar dari node tersebut, pindah ke ‘right’.
3. Jika data yang akan di- insert lebih kecil dari node tersebut, pindah ke ‘left’.
4. Ulangi langkah 3 dan 4 hingga node yang akan dipilih/pindah tidak ada.
5. Cek apakah data yang akan dimasukkan lebih besar / lebih kecil dari node tersebut. Jika lebih besar, maka di insert ke node ‘right’. Sebaliknya, jika lebih kecil maka di-insert ke ‘left’

3.) Delete

1. Data dicari dari atas atau dari Root
2. Jika "parent" adalah data yang dicari maka isi dari "parent" akan di delete
3. Jika data yang dimasukan lebih kecil dari Root maka data akan dicari ke "left" dari data diatasnya lalu jika benar maka akan di delete
4. Jika data yang dimasukan lebih kecil dari "left maka data akan dicari ke "right" dari data diatasnya lalu jika benar maka akan di delete
5. Langkah 2,3, dan 4 akan terus diulangi sampai data yang diinput user ditemukan atau semua data sudah di search