BINARY SEARCH TREE (BST)

Binary Search Tree (BST) merupakan sebuah konsep untuk penyimpanan data , yang dimana data yang disimpan dalam bentuk tree(pohon) yang setiap node yang memiliki anak maksimal 2 anak / 2 node. Kegunaan dari Binary Search Tree (BST) juga untuk melakukan pencarian dan melakukan sorting secara lebih efisien.

Ciri-citi dari Binary Search Tree (BST) adalah:
1.Value dari node kiri lebih kecil dibandingkan rootnya.
2.Value dari node kanan lebih besar dibandingkan dengan rootnya.
3.Setiap node harus memiliki value dan tidak ada valuenya yang berisikan double/float.

Fungsi-fungsi yang terdapat di dalam Binary Search Tree (BST):
1.Find(x) = Berfungsi untuk melakukan pencarian value (x) pada BST.
2.Insert(x) = Berfungsi untuk memasukkan value (x) yang baru ke dalam BST.
3.Remove(x) = Berfungsi untuk menghapus value (x) yang ada di dalam BST.

Fungsi Find(x) / Mencari Data
-) Memulai pencarian dari root.
-) Jika root adalah value yang kita cari , maka program selesai.
-) Jika x lebih besar dari root maka akan mencari secara rekursif ke tree sebelah kanan.
-) Jika x lebih kecil dari root maka akan mencari secara rekursif ke tree sebelah kiri.

Fungsi Insert(x) / Memasukkan Data
-)Dimulai dari root pertama.
-) Jika x lebih kecil dari node value kemudian mengecek dengan subtree sebelah kiri lakukan pengecekan secara rekursif.
-) jika x lebih besar dari node value kemudian mengecek dengan subtree sebelah kanan lakukan pengecekan secara rekursif.
-) Lakukan secara terus menerus hingga mendapatkan node yang kosong lalu diisi.

Fungsi Remove(x) / Menghapus Data
-) Jika value yang ingin dihapus merupakan leaf(daun) atau paling bawah. maka value akan langsung di remove.
-) Jika value yang ingin dihapus mempunyai 1 anak, maka hapus nodenya dan gabungkan anaknya ke parent yang belum dihapus.
-)Jika value yang akan dihapus mempunyai 2 anak, maka ada 2 cara yaitu:
   1.Node akan digantikan oleh node paling kiri dari subtree kanan.
   2.Node dapat digantikan oleh node paling kanan dari subtree kiri.