Binary Search Tree

Binary search tree merupakan suatu data structure yang memanfaatkan binary tree dalam penerapannya. perbedaannya pada binary tree data tidaklah tersortir, maka di binary search tree ini data akan di sortir.

Binary search tree yang benar 

(kiri) dan yang salah (kanan)

Node dibawah yang bercabang dari satu node lainnya (disebut child). child yang kiri akan lebih kecil daripada node yang mana ia berasal (disebut parent). child yang kiri juga akan lebih kecil dari node yang bercabang ke kanan (disebut sibling).

Pada contoh gambar sebelumnya, dapat dilihat bahwa child kiri dengan depth pertama lebih kecil dari parentnya (child kiri = 3, parent = 8). Hal ini berlaku seterusnya ke bawah.

child yang berada dari kanan parent nilainya selalu lebih besar dari parent tersebut. Pada gambar sebelumnya, dapat dilihat bahwa child kanan dengan depth pertama lebih kecil dari parentnya (child kanan = 10, parent = 8). Hal ini juga berlaku seterusnya sama seperti kasus child yang kiri.

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

penerapan code pada C/C++:

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, pada kode dapat dilihat bahwa setiap kali belum ada data, akan diciptakan node yang akan diisi oleh data yang baru. kalau sudah terdapat data dalam node parent, maka akan dibandingkan data tersebut dengan node yang sudah ada. kalau data lebih kecil, akan dibuat node di sisi kiri parent untuk menjadi tempat data baru tersebut. sebaliknya, jika data baru tersebut lebih besar dari parent, maka akan dibuat node baru pada sisi kanan parent yang akan menjadi letak data baru tersebut.

SOURCE:

- https://www.programiz.com/dsa/binary-search-tree