Binary Search Tree

Binary Search Tree

Binary Search Tree mempunyai 2 aturan yaitu:
1. Jika value node lebih besar dari node, maka node tersebut akan menjadi leaf kanan node tersebut.
2. Jika value node lebih kecil dari node, maka node tersebut akan menjadi leaf kiri node tersebut.

Ini adalah contoh kode create dan insert untuk binary search tree:
#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *left, *right;
};

// Function untuk membuat node baru
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

/* Function untuk insert */
struct node* insert(struct node* node, int key){
if (node == NULL) {
return newNode(key);
}

if (key < node->key){
node->left = insert(node->left, key);
}else if (key > node->key){
node->right = insert(node->right, key);
}

return node;
}

int main(){
/* Kita akan membuat binary search tree seperti ini
50
/ \
/         \
30        70
/ \         / \
20 40   60  80 */

struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}

Contoh kode delete untuk binary search tree;
 // C program to demonstrate delete operation in binary search tree
#include<stdio.h>
#include<stdlib.h>

struct node
{
int key;
struct node *left, *right;
};

struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

/* Function untuk insert*/
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}

struct node * minValueNode(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current && current->left != NULL)
current = current->left;

return current;
}

/* Function untuk delete */
struct node* deleteNode(struct node* root, int key)
{
// base case
if (root == NULL) {
            return root;
        }

if (key < root->key) {
root->left = deleteNode(root->left, key);
        }else if (key > root->key) {
root->right = deleteNode(root->right, key);
        } else{ 
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}

int main()
{
/* Kita akan membuat binary search tree seperti ini
           50
 / \
      30 70
      / \         / \
   20 40   60 80 */
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);

printf("Inorder traversal of the given tree \n");
inorder(root);

printf("\nDelete 20\n");
root = deleteNode(root, 20);
printf("Inorder traversal of the modified tree \n");
inorder(root);

printf("\nDelete 30\n");
root = deleteNode(root, 30);
printf("Inorder traversal of the modified tree \n");
inorder(root);

printf("\nDelete 50\n");
root = deleteNode(root, 50);
printf("Inorder traversal of the modified tree \n");
inorder(root);

return 0;
}

Sumber kode: 

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/