Pertemuan ke 5 - Binary Search Tree - 2101662032 - Arya Surya Sabara Cia

BINARY SEARCH TREE

1. PENGERTIAN BINARY TREE
   Binary Tree adalah struktur data yang hampir mirip dengan linked list untuk menyimpan koleksi dari data. Linked list dapat dianalogikan sebagai rantai linear sedangkan Binary tree bisa digambarkan sebagai rantai tidak linear, binary tree dikelompokkan menjadi unordered binary tree dan ordered binary tree.
   Binary Search Tree adalah tree yang terurut. ada beberapa aturan yang perlu diperhatikan saat membuat sebuah BST,yaitu:
   1. Semua data dibagian kiri sub-tree dari node A selalu lebih kecil dari data dalam node A itu sendiri.
   2. Semua data dibagian kanan sub-tree dari node A selalu lebih besar atau sama dengan data dari dalam node A itu.
2. PEMBENTUKAN BST
   
   Bila diketahui sederetan data 5, 3, 7, 1, 4, 6, 8, 9 maka proses inserting (memasukkan) data tersebut dalam algoritma BST langkah per langkah adalah sebagai berikut.
   
   
   Langkah 1: Pemasukan data 5 sebagai root( akar)
   
   
   
   Langkah 2: Pemasukan data 3 disebelah kiri simpul 5 karena 3 < 5.
   
   
   
   Langkah 3: Pemasukan data 7 disebelah kanan simpul 5 karena 7 > 5.
   
   
   
   
   
   Langkah 4:  Masukkan angka 1. Karena 1 lebih kecil dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 3 dan 1 lebih kecil dari 3 maka 1 disisipkan disebelah kiri simpul 3,sehingga 3 menjadi parent dari 1, dan 1 menjadi leaf.
   
   
   
   
   
   Langkah 5:   Pemasukan data 4.
   
   
   
   
   
   
   
   Langkah 6:   Pemasukan data 6. Karena data 6 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan data 6 lebih kecil dari data 7 maka data 6 disisipkan disebelah kiri simpul 7.
   
   
   
   
   
   
   
   
   
   Langkah 7:   Pemasukan data 8. Karena data 8 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan karena data 8 lebih besar dari data 7 maka data 8 disisipkan disebelah kanan simpul 7. 
   
   
   
   
   
   
   
   
   
   Langkah 8:   Pemasukan data 9. Karena data 9 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 7 dan karena data 9 lebih besar dari data 7 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 8, karena data 9 lebih besar dari 8 maka data 9 disisipkan disebelah kanan simpul 8.
   
   
   
   
   
   
   
3. PENGHAPUSAN DALAM BST
   Dalam BST, apabila kita ingin menghapus data didalamnya, terdapat beberapa kondisi yang mungkin terjadi:
   1. Data yang kita hapur merupakan leaf
   2. Data yang kita hapus mempunyai 1 child
   3. Data yang kita hapus mempunyai 2 child

              a. Data berupa leaf
              Jika data yang ingin kita hapus merupakan leaf, maka kita dapat langsung menghilangkan nya (                            free(curr)) dan membuat turunan dari parentnya menjadi NULL ( tidak ada )

              b. Data ada 1 child
              Jika data yang ingin kita hapus mempunyai 1 child, maka kita terlebih dulu menyambungkan child dari                data tersebut ke parent dari data yang ingin kita hapus, kemudian kita dapat mem free data yang ingi                    kita hapus

              c. Data ada 2 child
              Jika data yang ingin kita hapus mempunyai 2 child,maka pertama kita harus mencari data dengan nilai terbesar di sebelah kiri data yang ingin kita hapus,kemudian membuatnya menggantikan posisi data yang ingin kita hapus, apabila data yang menggantinya memiliki child, child tersebut dapat berada di sebelah kiri atau kanan posisi data yang menggantikannya tergantung nilainya. Kemudian kita dapat free data yang ingin dihapus

2101662032 - Arya Surya Sabara Cia