Binary Search Tree

               Binary Search Tree (BST) adalah sebuah struktur data yang dibuat agar pencarian(searching), pengurutan(sorting), pemasukkan(insertion) dan penghapusan(deleteion) dapat dilakukan lebih cepat dan juga lebih mudah. Binary Search Tree juga seringkali disebut sorted version of Binary Tree atau dapat kita artikan sebagai Binary Tree yang diurutkan. Binary Search Tree biasanya dibuat dengan skema sebagai berikut :  

• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih kecil dibanding nilai yang ada di node atasnya diletakkan di node sebelah kiri
• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih besar dibanding nilai yang ada di node atasnya diletakkan di node sebelah kanan
• *diasumsikan nilai dari node-node berbeda-beda

Operasi-operasi pada Binary Search Tree 

• Searching: Pencarian suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                          berikut:    1. Mulai dari node teratas atau root  

                                             2. Cek apakah node teratas atau root adalah nilai yang dicari(jika iya,                                                         maka program telah selesai, jika tidak lanjutkan ke langkah 3)

                                             3. JIka nilai yang dicari lebih kecil dibanding node atasnya atau root

                                                 maka lakukan pencarian secara recursive ke kiri dan sebaliknya jika

                                                 jIka nilai yang dicari lebih besar dibanding node atasnya atau root 

                                                 maka lakukan pencarian ke kanan secara recursive

• Insertion: Memasukkan suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                     berikut:       1. Mulai dari node teratas atau root  

                                              2. Jika nilai yang ingin dimasukkan lebih kecil dibanding node atasnya                                                      atau root masukkan angka ke subtree sebelah kiri dari root dan

                                                  sebaliknya jika nilai yang ingin dimasukkan lebih besar dibanding

                                                  node atasnya atau root  masukkan angka ke subtree sebelah kanan dari

                                                  root

                                               3. Ulangi sampai nilai yang ingin dimasukkan menemukan tempat

                                                   kosong untuk dapat nilai tersebut tempati

• Deletion: Menghapus suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                         berikut:        1. Cek node-node yang ada, jika node yang ingin dihapus idak                                                         memiliki subtree atau anak, hapus langsung node tersebut.
                                       2. Jika node yang ingin dihapus memiliki 1 subtree atau anak, hapus                                                langsung node tersebut, lalu sambungkan subtree atau anak node                                                   tersebut dengan node di atasnya atau parent. 

                                                3. Jika node yang ingin dihapus memiliki 2 subtree atau anak, cari anak

                                                    dari node tersebut yang menempati posisi di paling kanan subtree

                                                    bagian kiri lalu tempatkan anak tersebut di node yang ingin dihapus,

                                                    lalu hapus posisi anak tersebut secara recursive.