Binary Search Tree

BINARY SEARCH TREE

Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. BST juga dikenal sebagai binary tree dengan versi terurut.
Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Aturan dalam BST :
1. Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
2. Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Terdapat 3 oeprasi dasar pada BST:
1. find(x) : untuk mencari key x dalam BST

void find(Node **current, int value){
if((*current) != NULL){
if(value < (*current)->val){
find(&(*current)->left, value);
}
else if(value > (*current)->val){
find(&(*current)->right, value);
}
else{
printf("&d is found", value);
}
}
else{
printf("%d is Not Found.", value);
}
}

2. insert(x) : untuk menaruh key baru pada BST

void insert(Node **current, int value){
if((*current) == NULL){
(*current) = (struct Node*) malloc (sizeof (Node));
(*current)->val = value;
(*current)->left = (*current)->right = NULL;
}
else{
if(value < (*current)->val){
insert(&(*current)->left, value);
}
else{
insert(&(*current)->right, value);
}
}
}

3. remove(x) : untuk menghapus key x pada BST

void remove(Node **current, int value){
if((*current) == NULL){
printf("%d not found in the tree\n", value);
flag = 0;
}
else{
if((*current)->val == value){
if(flag == 0){
if((*current)->left == NULL){
if((*current)->right == NULL){
(*current) = NULL;
}
else{
int mostleftval = rightLeaf(&(*current)->right);
(*current)->val = mostleftval;
}
}
else{
int mostrightval = rightLeaf(&(*current)->right);
(*current)->val = mostrightval;
}
}
else if(flag == 1){
int mostleftval = rightLeaf(&(*current)->right);
(*current)->val = mostleftval;
}
else{
int mostrightval = rightLeaf(&(*current)->right);
(*current)->val = mostrightval;
}
flag = 0;
printf("%d has been deleted from tree\n", value);
}
else{
if(value < (*current)->val){
flag = -1;
remove(&(*current)->left, value);
}
else{
flag = 1;
remove(&(*current)->right, value);
}
}
}
}

Ada 3 cara melakukan penelusuran data (transversal) pada BST :
1. PreOrder : Print data, telusur ke kiri, telusur ke kanan
2. InOrder : Telusur ke kiri, print data, telusur ke kanan
3. Post Order : Telusur ke kiri, telusur ke kanan, print data


sumber :
https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
slide binusmaya