Binary Search Tree

Binary Search Tree

BST merupakan suatu metode menganalisa node yang menggunkan konsep seperti pohon yaitu memiliki ranting. Ranting tersebut dibagi menjadi 2 macam, yaitu ranting sebelah kiri dan kanan, dimana ranting sebelah kiri merupakan kumpulan node yang lebih kecil dari induknya yaitu yang bagian tengah dan terdapat juga ranting yang sebelah kanan dimana akan berisi kumpulan node yang valuenya lebih besar dari node induknya.

Ciri - ciri BST:

- Menggunkan konsep relationship antara parent dan child

- Setiap parent node dapat mempunyai nol anak sampai dengan 2 anak(satu di sebelah kiri dan satu di sebelah kanan)

- Setiap subtree mempunyai subbranches di sebelah kanan maupun di sebelah kirinya

- Setiap node memilki nilai valuenya sendiri

- Node yang terletak di sebelah kiri dari si induk memilki value lebih kecil dari si induk dan lebih besar di sebelah kanan si induk.

Tipe - tipe BST :

- Full Binary Tree : BST yang dimana setiap node memilki anak (kecuali yang paling akhir -> leaves)

- Complete Binary Tree : BST yang setiap level nya memilki anak kecuali yang terakhir 

- Balanced / Perfect Binary Tree : setiap node memilki level yang sama dan terdapat anak dalam setipa node

Metode Insert :

- Misalkan kira ingin memsukkan node yang nialinya 10, kita compare dulu dengan si induk, apabila si induk nialinya lebih besar dari nilai yang kita cari maka kita mulai mencari dari anak yang sebelah kiri dan kemudian kita compare lagi, nilai 7 memilki nilai yang lebih keci dari pada 10 maka kita compare lagi dengan anak yang sebelah kanannya yaitu 9 dan memilki nilai yang lebih kecil lagi maka kita cek dulu apakah si 9 memilki anak atau tidak , jika tidak ada maka kita masukkan 10 menjadi anak dari si 9

Metode Seraching : 

Misalkan kita ingin mencari si nilai 10, maka kita comparedulu apakah nilai si induk lebih besar aau lebih besar dari si induk, apabila nilainya lebih besar maka kita compare lagi dengan si anaknya yang sebelah kiri apabila nilai anak yang sebelah kiri lebih kecil atau tidak sama dengan si 10 maka kita compare dengan anaknya yang sebelah kanannya dan di compare terus sampai nilainya ketemu. Apabila nilai yang dicari tidak ketemu maka akan direturn -1.

Metode Delete : 

Case 1 : Node yang ingin dihapus tidak memilki anak sama sekali maka langsung dihapus saja si value tesebut.

Case 2 : Node yang ingin dihapus memilki hanya satu anak maka anaknya langsung disambungkan dengan si parent dari node yang dihapus.

Case 3 : Node yang ingin dihapus memilki dua anak (child)

Ada 2 cara  : 

- In Order Predecessor : menghpus node tersebut dan digantikan dengan nilai terbesar dari node sebelah kiri dari node yang dihapus

- In Order Successor : menghapus node tersebut dan digantikan dengan nilai tersbesar dari node sebelah kanan dari node yang dihapus