BINARY SEARCH TREE

Binary Search Tree (BST) merupakaan salah satu struktur data yang digunakan untuk menyimpan data yang mempermudah proses pencarian data (searching), memasukkan data berurut (insertion) dan menghapus data (deletion). Binary Search Tree memiliki bentuk seperti Tree dan setiap data harus memiliki nilai yang berbeda dimana data disebut dengan Node. Node yang berada diposisi paling atas disebut dengan Root. Dalam BST, node akan terhubung dengan node lainnya sebanyak maksimalnya 2. Kedua node memiliki nama left subtree dan right subtree. Left subtree harus memiliki nilai lebih kecil dari nilai di node dan right subtree harus memiliki nilai lebih besar dari node. Node yang tidak memiliki left maupun right subtree disebut leaf.

Searching

Misalkan ingin mencari integer dengan value n.

Searching dimulai dari Root. Apabila n bernilai sama dengan Root, pencarian data akan berhenti karena data sudah ditemukan. Namun, apabila n bernilai lebih kecil dari Root, maka pencarian berlanjut ke left subtree dan sebaliknya apabila n lebih besar, maka pencarian berlanjut ke right subtree sampai data ditemukan.

Insertion

Misalkan ingin memasukkan integer dengan value n.

Jika Root masih kosong, maka data akan menjadi Root.

Jika n bernilai lebih kecil dari Root, n akan menjadi left subtree. Sebaliknya, jika n bernilai lebih besar dari Root, n akan menjadi right subtree. Dan seterusnya hingga menemukan tempat kosong dan data yang baru dimasukkan akan selalu menjadi leaf.

Deletion
Misalkan ingin menghapus integer dengan value n.
Jika n terdapat pada Root, maka dapat mengambil data pada leaf yang memiliki nilai paling besar dari left subtree atau pada leaf yang memiliki nilai paling kecil dari right subtree. Maka data tersebut akan menggantikan n dan leaf tempat sebelumnnya akan dihapus. Apabila n terdapat pada leaf, maka dapat langsung dihapus leafnya.