Binary Search Tree (BST)

Struktur data binary search tree memberikan fitur searching dan sorting yang lebih cepat. insert dan delete yang lebih mudah juga. 
Aturan penempatan node : 
1. Untuk node yang lebih kecil dari node yang dibandingkan maka node tersebut ditempatkan dikiri
2. Untuk node yang lebih besar dari node yang dibandingkan maka node tersebut ditempatkan dikanan
3. Setiap node nilainya berbeda
4. Perbandingan mulai dari root, terus turun sampai dapat tempat kosong


Operasi pada BST
1. search(x)
2. insert(x)
3. remove(x)

1. Search
Misalnya nilai yang mau kita cari adalah x
 - Mulai dari root
 - Jika root mengandung x maka proses selesai
 - Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari  secara rekursif pada subtree kanan
2. Insert
 Misalnya nilai yang ingin kita masukkan adalah x
 - Proses mulai dari root
 - Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari  secara rekursif pada subtree kanan
 - cari sampai dapat node kosong dan taruh x(X akan selalu jadi leaf baru)

3. Deletion 
Ada 3 kasus pada saat delete:
 - Jika yang didelete adalah leaf, maka langsung didelete
- Jika node yang mau dihapus punya child, maka node tersebut dihapus dan hubungkan child dengan parentnya node yang dihapus.
- Jika node yang dihapus memiliki 2 children, cari child paling kanan pada subtree kiri (node nilai terbesar di subtree kiri alias 'P'), tukar nilai dari node dengan nilai pada P dan hapus P secara rekursif.

Source Code BST:
#include <stdio.h>
#include <stdlib.h>

struct Node{
int value;
Node *left, *right;
}*root=NULL;

Node* newData(int value){
Node *temp = (Node*) malloc(sizeof(Node));
temp->value = value;
temp->right=temp->left = NULL;
return temp;
}

Node *insertData(Node *curr, int value){
if(curr==NULL) return newData(value);
else{
if(value < curr->value){
curr->left= insertData(curr->left, value);
}
else if (value > curr->value){
curr->right = insertData(curr->right,value);
}
}
return curr;
}
// fungsi untuk mendapatkan successor (node paling kiri)
Node* successor(Node *curr){
if(curr==NULL) return NULL;
else{
while(curr->left){
curr = curr->left;
}
return curr;
}
}

Node *deleteData(Node *curr, int value){
if(curr==NULL) return NULL;
else{
if(value < curr->value){
curr->left= deleteData(curr->left, value);
}
else if (value > curr->value){
curr->right = deleteData(curr->right,value);
}else{
if(curr->left && curr->right){
Node *temp = successor(curr->right);

curr->value=temp->value;
curr->right = deleteData(curr->right,temp->value);
}
else{
Node *temp= (curr->left) ? curr->left : curr->right;

if(temp!=NULL){
return temp;
}else{
free(curr);
return NULL;
}
}
}
}
return curr;
}

Node* search(Node *curr, int value){
if(curr==NULL) return NULL;
else{
if(value < curr->value){
search(curr->left,value);
}else if(value  > curr->value){
search(curr->right, value);
}else if( curr->value==value){
return curr;
}
}
}
//fungsi untuk print isi pada BST bisa secara preOrder //maupun postOrder
void inOrder(Node *node){
if(node==NULL) return;
else{
inOrder(node->left);
printf("%d ", node->value);
inOrder(node->right);
}
}

int main(){

root = insertData(root, 10);
root = insertData(root, 5);
root = insertData(root, 11);
inOrder(root);

Node* temp =search (root,10);
if(temp){
printf("found");
}
else{
printf("not found");
}
return 0;
}