Binary Search Tree

Binary Search Tree atau BST adalah salah satu implementasi struktur data dinamis yang non-linear dalam bentuk binary tree yang datanya dalam kondisi terurut atau sorted. BST memungkinkan proses pencarian, penambahan, ataupun penghapusan data menjadi lebih cepat dengan rata-rata kompleksitas waktu O(log n) walaupun dalam kondisi tertentu, dapat memiliki kompleksitas O(n) atau sama seperti kompleksitas struktur data linear. Hal tersebut dapat terjadi apabila Binary Tree yang terbentuk tidak seimbang atau menjadi Skewed Binary Tree (bentuk yang sudah dijelaskan di pertemuan sebelumnya). Efisiensi Binary Search Tree dapat dilakukan dengan banyak cara salah satunya AVL, namun di pertemuan kali ini kita hanya akan membahas Binary Search Tree dan operasi-operasi yang dimilikinya. 

Umumnya ciri-ciri BST adalah sebagai berikut, 

• Setiap node memiliki value dan tidak ada value yang sama / double
• Value yang ada di sebelah kiri tree memiliki nilai yang lebih kecil dari root nya
• Value yang ada di sebelah kanan tree memiliki nilai yang lebih besar dari root nya
• Kiri dan kanan tree bisa menjadi root lagi atau bisa memiliki anak / Child lagi, sehingga seperti rekursif

Binary Search Tree

BST memiliki 3 proses utama dalam pengimplementasiannya. Proses-proses tersebut adalah

1.     Find(x) : find value x di dalam BST

2.     Insert(x) : memasukkan value baru x ke dalam BST (push)

3.     Delete(x) : menghapus value x dalam BST (pop)

Operasi: Search BST

dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

Operasi: Insertion BST

Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :

• Dimulai dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
• Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

Operasi: Delete ( Remove )

akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

• Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau cari dari right sub-tree anak kiri paling terakhir(leaf)(kanan,kiri)

Lalu untuk melakukan print all kita akan pakai yang namanya function in-order, yaitu melakukan traverse ke kiri sampai habis lalu print kemudian cari ke kanan baru print lagi 

Contoh Full Source Code Binary Search Tree :

(Kalau pusing lihat format tulisannya, silahkan di copy lalu cari di google Source Code Beautifyer)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Stuff{
int code;
char name[100];
Stuff *left, *right;
} *root;

Stuff *newNode(int code, char name[100]){
Stuff *node = (Stuff*)malloc(sizeof(Stuff));
node->code = code;
strcpy(node->name, name);
node->left = node->right = NULL;
return node;
}

Stuff *insert(Stuff *root, int code, char name[100]){
if(root == NULL)
return newNode(code, name);
else if(root->code > code)
root->left = insert(root->left, code, name);
else
root->right = insert(root->right, code, name);
return root;
}

Stuff *remove(Stuff *root, int code){
if(root == NULL)
return root;
else if(root->code > code)
root->left = remove(root->left, code);
else if(root->code < code)
root->right = remove(root->right, code);
else{
//kalo dia punya 1 anak atau ga punya anak
if(root->left == NULL || root->right == NULL){
Stuff *temp = root->left != NULL?
root->left : root->right;
//kalo punya 1 anak
if(temp != NULL){
*root = *temp;
}
//kalo tidak punya anak
else{
temp = root;
root = NULL;
}
free(temp);
}
//kalo dia punya 2 anak
else{
Stuff *temp = root->left;

while(temp->right != NULL)
temp = temp->right;

root->code = temp->code;
strcpy(root->name, temp->name);

root->left = remove(root->left, temp->code);
}
return root;
}
}

Stuff *removeAll(Stuff *root){
if(root != NULL){
removeAll(root->left);
removeAll(root->right);
free(root);
}
return NULL;
}

void inOrder(Stuff *root){
if(root != NULL){
inOrder(root->left);
printf("%d %s\n", root->code, root->name);
inOrder(root->right);
}

}

int main(){

root = insert(root, 5, "Hammer");
root = insert(root, 3, "Guitar");
root = insert(root, 10, "Harmonica");
root = insert(root, 2, "Card");
root = insert(root, 1, "Cars");
root = insert(root, 4, "Piano");

inOrder(root);
printf("\n");

root = removeAll(root);
inOrder(root);

return 0;

}

Refrensi :
- https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
- https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html