Binary Search Tree (BST)

Binary Search Tree

Binary search tree (BST) adalah suatu data struktur yang memanfaatkan binary tree sebagai strukturnya. Konsep binary search tree sangatlah simple, jika binary tree data tidak disortir, pada binary search tree data akan disortir.

Contoh Binary Search Tree (BST)

Bisa kita lihat pada contoh diatas setiap tangan kiri suatu node akan lebih kecil dari node. 

1. Tangan kiri dari node 8 adalah node 3, dimana 8 lebih kecil daripada 3.  

2. Tangan kiri 3 adalah 1, dimana 1 lebih kecil daripada 3.

3. Dan seterusnya...

Kita juga dapat lihat bawah setiap tangan kanan dari sebuah node adalah bilangan yang lebih besar daripada node.

1. Tangan kanan dari node 8 adalah 10, dimana 10 lebih besar daripada 8.

2. Tangan kanan 10 adalah 14, dimana 14 lebih besar daripada 10.

3. Dan seterusnya...

Nah, itulah definisi dari Binary search tree, pada umumnya tangan kiri akan lebih kecil daripada node, tangan kanan lebih besar daripasa node, tetapi hal itu bisa dibalik sesuai dengan sang programmer yang memprogramnya dan juga kebutuhannya.

Lalu, Apa perbedaan dari Binary search tree daripada binary tree biasa?

1. Data yang disortir akan terlihat rapi.

2. Pencarian data akan lebih mudah, dengan bisa menggunakan binary search.

3. Pembuatan binary search tree lebih rumit daripada binary tree.

4. Data akan terstruktur.

Berikut adalah sedikit contoh code Binary Search tree dengan dioutput menggunakan Inorder traversal:


Main code:

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

struct node{
int value;
struct node *left;
struct node *right;
}*root;

// function membuat dan mengassign value ke node baru
struct node *newNode(int data){

struct node *temp = (struct node*)malloc(sizeof(struct node));

temp->value = data;
temp->left = NULL;
temp->right = NULL;

return temp;
}

// insert node
void insert(int data, struct node* curr){


if(root == NULL){

root = newNode(data);
}
else if(data < curr->value){ 
if(curr->left == NULL) curr->left = newNode(data);
else insert(data, curr->left);


}
else if(data > curr->value){
if(curr->right == NULL) curr->right = newNode(data);
else insert(data, curr->right);


}


}


void printInorder(struct node *curr){

if(curr == NULL) return;

printInorder(curr->left);
printf("%d ", curr->value);
printInorder(curr->right);

}

int main(){
 
/*    gambaran

    8
   /   \
 2     18
/ \      /
1  5   9

*/
// inorder = left,root,right


insert(8,root);
insert(2,root);
insert(18,root);
insert(5,root);
insert(9,root);
insert(1,root);
printInorder(root);

printf("\n\n");
 // tes print 5
printf("%d", root->left->right->value);


return 0;
}

Output:

1 2 5 8 9 18

5


Nah, diatas merupakan contoh code BST yang mempunyai function insert dan juga print. Bisa kita lihat jika kita insert data pertama, maka data pertama tersebut akan menjadi root dari tree kita. Sehingga jika kita insert data lebih kecil dari node, ia akan ke tangan kiri dan sebaliknya jika kita insert data lebih besar dari node ia akan ke tangan kanan.