Binary Search Tree

Binary Search Tree adalah sebuah pohon biner struktur data yang dimana:
- Semua simpul mempunyai nilai
- Sub pohon kiri mempunyai nilai yang lebih kecil daripada nilai simpul
- Sub pohon kanan mempunyai nilai yang lebih besar daripada nilai simpul

Operasi yang dapat dilakukan untuk suatu Binary Search Tree adalah Find, Insert, dan Remove.

1. Find
- Pencarian dimulai di akar, apabila nilai akar sama dengan nilai yang kita cari maka proses pencarian langsung stop.

- Jika nilai yang kita cari lebih kecil daripada nilai akar, lakukan pencarian secara rekursif ke bagian kiri sub pohon biner. Namun, jika nilai yang kita cari lebih besar daripada nilai akar, lakukan pencarian secara rekursif ke bagian kanan sub pohon biner.

2. Insert
- Dimulai dari akar
- Jika nilai yang kita input lebih besar daripada nilai akar, maka masuk ke sub pohon kanan. Namun, jika nilai yang kita input lebih kecil daripada nilai akar, maka masuk ke sub pohon kiri. Step ini diulangi hingga kita menemukan tempat kosong dimana kita menaruh nilai yang kita input disitu.

3. Deletion
Terdapat 3 kondisi yang harus diperhatikan:
- Jika nilai yang kita ingin hapus berada pada di daun, maka kita tinggal delete langsung.
- Jika nilai yang kita ingin hapus terdapat dalam simpul yang memiliki 1 anak, maka kita hapus nilai tersebut dan menggantikannya dengan cara menghubungkan anak ke orang tuanya
- Jika nilai yang kita ingin hapus terdapat dalam simpul yang memiliki 2 anak. cari anak yang paling kanan dari sub pohon kiri, menggantikan posisi anak dengan nilai yang kita inginkan kemudian menghapus nilai yang kita inginkan secara rekursif