Binary Search Tree(BST)

Kali ini , kita belajar Binary Search Tree / BST. Kita pertama - tama akan membahas struktur dasar Tree terlebih dahulu . Tree (pohon) adalah salah satu bentuk struktur ata yang menggambarkan hubungan hierarki antar elemen-elemennya(seperti relasi one to many).

Nah... Binary Tree atau pohon biner adalah suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree terhebut harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak 2 child / anak simpul (anak kiri ,anak kanan). Dan saat Menginsert nya dia masih belum tersusun rapi.

Binary Search Tree adalah tree yang terurut (ordered Binary Tree) / Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang di simpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah sebagai patokannya. Binary Tree terdiri dari 1. simpul utama yang disebut dengan istilah root, dan setiap root mempunyai 2 child. 

2. 2 child yang memiliki 1 root yang sama di sebut Sibling , 

3. suatu root yang tidak memiliki child sama sekali di sebut leaf

Data yang tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata- rata kompleksitas sebesar O(log n),namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.

2 aturan yang harus di penuhi pada saat data di atur dalam BST :

1. Semua data di bagian kiri sub-tree dari node  selalu lebih kecil dari data dalam node t itu

2. semua data dibagian kanan sub-tree dari node  selalu lebih besar atau sama dengan data dalam node 

Operasi BST : 

-Insertion 

1. Dimulai dari root 

2. Jika x lebih kecil dari key kemudian cek dengan sub-tree sebelah kiri , lakukan pengecekan secara rekursif.

3. Jika x lebih besar dari key kemudian cek dengan sub-tree sebelah kanan ,lakukan pengecekan secara rekursif.

4. Ulangi sampai menemukan node yang kosong untuk memasukkan value 

-Delete

1. Jika value yang ingin dihapus adalah leaf , langsung delete saja

2. Jika value yang akan dihapus mempunyai satu child , hapus nodenya dan gabungkan childnya ke parent value yang dihapus.

3. Jika value yang akan di hapus adalah noode yang mempunyai 2 child , maka cari dari left sub-tree ,kemudian bandingan dengan yang kanan .