Binary Search Tree
Binary Search Tree adalah salah satu data struct yang mensupport kecepatan dalam function searching , sorting, dan deletion . BST merupakan salah satu jenis Binary Tree hanya saja BST hasilnya pasti sudah tersorting dimana untuk node x pada Tree itu untuk bagian kiri untuk elemen yang mempunyai nilai lebih kecil daripada x sedangkan untuk bagian kanan berisi elemen yang lebih besar daripada nilai x.Basic Operation of Binary Search Tree :
- Searching
- Insertion
- Deletion ( Merupakan operasi yang cukup komplek dan memerlukan ketelitian dalam pemrograman supaya hasil sesuai dengan yang di harapkan)
Point utama yaitu pada Binary Search Tree tidak ada node yang sama atau terduplikasi.
Gambaran penjelasan bentuk Binary Search Tree ( BST)
Searching Operation :
Merupakan operasi yang relatif lebih mudah daripada operasi lainnya karena hanya mencari suatu data pada BST. Jika data yang dicari lebih kecil daripada root maka root akan lanjut ke kiri tapi jika sebaliknya maka root akan lanjut ke kanan selama data ditemukan atau setelah pengecekan data BST dimana akan dilakukan secara recursive function.
if(Node==NULL||Node->nilai==angka){
return Node;
}
if(angka < Node->nilai){
return Searchdata(Node->left,angka);
}else if(angka > Node->nilai){
return Searchdata(Node->right,angka);
}
}
Insertion Operation :
Operasi ini untuk memasukan data baru ke dalam Binary Search Tree. Dimana program akan berlangsung sampai data baru masuk ke dalam Binary Search Tree. Lokasi / letak dari data yang dimasukan tergantung dari besar nilainya. Jika nilai data baru lebih kecil daripada current root maka data baru akan terletak di bagian kiri jika tempat bagian kiri dari current root kosong dan sebaliknya jika lebih besar maka data baru tersebut akan terletak di bagian kanan jika tempat bagian kanan dari current root itu kosong. Poin penting yaitu jika nilai data baru merupakan nilai yang sama dengan data yang telah ada di dalam BST maka data tidak akan masuk kembali ke dalam data BST.
struct node *Insertdata(struct node* Node,int angka){
if(Node==NULL){
return createNode(angka);
}
if(angka < Node->nilai){
Node->left = Insertdata(Node->left,angka);
}else if(angka>Node->nilai){
Node->right = Insertdata(Node->right,angka);
}
return Node;
}
struct node *Insertdata(struct node* Node,int angka){
if(Node==NULL){
return createNode(angka);
}
if(angka < Node->nilai){
Node->left = Insertdata(Node->left,angka);
}else if(angka>Node->nilai){
Node->right = Insertdata(Node->right,angka);
}
return Node;
}
Deletion Operation :
Dalam delete operation ada 3 kemungkinan yang akan ditemui yaitu :
- Jika data yang ingin dihapus terletak pada leaf dari BST : Secara simpel tinggal menghapus data tersebut dengan free();
- Data yang ingin dihapus memiliki satu child : Mengkopi data child ke node dan menghapus node childnya
- Data yang ingin dihapus memiliki dua child : Penjelasan simpelnya seperti cara untuk data yang punya satu child tapi sebelumnya perlu mencari dahulu inorder successor / inorder predecessor dan mengkopi data tersebut ke node lalu menghapus inorder successor/ inorder predecessor nya.
struct node *deletion(struct node *Node,int angka){
if(Node==NULL){
return Node;
}
if(angka < Node->nilai){
Node->left = deletion(Node->left,angka);
}else if (angka > Node->nilai){
Node->right = deletion(Node->right,angka);
}else{
if(Node->left == NULL || Node->right == NULL){
struct node *tempNode = NULL;
if(Node->left!=NULL){
tempNode = Node->left;
}else{
tempNode = Node->right;
}
//gak ada child
if(tempNode==NULL){
tempNode = Node;
Node = NULL;
free(tempNode);
//child ada satu
}else{
*Node = *tempNode;
free(tempNode);
}
//case ada 2 anak
}else{
struct node *tempNode = predecessor(Node);
Node->nilai = tempNode->nilai;
Node->left = deletion(Node->left,tempNode->nilai);
}
}
return Node;
}
Referensi :
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
if(Node==NULL){
return Node;
}
if(angka < Node->nilai){
Node->left = deletion(Node->left,angka);
}else if (angka > Node->nilai){
Node->right = deletion(Node->right,angka);
}else{
if(Node->left == NULL || Node->right == NULL){
struct node *tempNode = NULL;
if(Node->left!=NULL){
tempNode = Node->left;
}else{
tempNode = Node->right;
}
//gak ada child
if(tempNode==NULL){
tempNode = Node;
Node = NULL;
free(tempNode);
//child ada satu
}else{
*Node = *tempNode;
free(tempNode);
}
//case ada 2 anak
}else{
struct node *tempNode = predecessor(Node);
Node->nilai = tempNode->nilai;
Node->left = deletion(Node->left,tempNode->nilai);
}
}
return Node;
}
Referensi :
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
