Skip to main content

Binary Search Tree (BST)

Binary Search Tree or also known as Ordered or Sorted Binary Tree is a type of data structure that store a value like a tree. A Binary Search Tree allow fast searching, adding, and deleting node. This is cause by The Binary Search Tree keep their node in a sorted order so that searching can be done using the binary search method without the additional Sorting needed because it is already sorted by nature.

Operation

1. Searching :
First and foremost we check if the tree is empty or not. If the tree is empty then the process is cancelled but if the tree is not empty then we check if our key is greater or less then the root key. If it's greater then our node lies in the right subtree and vice versa. This operation can be done in a recursive or iterative way.

//A function that is used to search a node in the BST
Node *search(Node *root, int val){
//base case
//if the tree is empty or the value is at the root
if(root==NULL || root->value==val){
return root;
}
//if the val is greater than the root value, then go right
if(root->value<val){
return search(root->right, val);
}
//if the val is less than the root value, then go left
return search(root->left, val);
}

2. Adding
Like Searching we first make sure if our tree is empty or not. If it's empty then make the node into our root. If it's not empty then we either go left if our key is less then the root key, or go right if our key is greater then the root key.

//A fucntion to insert a new node onto the BST
Node *insert(Node *node, int val){
//if the tree is empty then return the new node
if(node==NULL){
return newNode(val);
}
//else travel down the tree
if(val>node->value){
node->right = insert(node->right,val);
}else if(val<node->value){
node->left = insert(node->left,val);
}
//return the node (unchanged) pointer
return node;
}

3. Delete
In deleting a node in BST there are some condition :
1. If a node has only 1 child or no child at all
2. If a node has 2 child

if the node that we wanted to delete has 2 child we have to replace it with it's successor (The most left node in the right subtree) or it's predecessor (The most right node of the left subtree) so that or tree still retain it's ordered (Still sorted in the right way)


//A function that is used to search a node in the BST
Node *search(Node *root, int val){
//base case
//if the tree is empty or the value is at the root
if(root==NULL || root->value==val){
return root;
}
//if the val is greater than the root value, then go right
if(root->value<val){
return search(root->right, val);
}
//if the val is less than the root value, then go left
return search(root->left, val);
}

//A fuction to get the successor(The smallest node in the right subtree of the node)
Node *getSuccessor(Node *node){
Node *curr = node;
//loop to find the successor
while(curr && curr->left!=NULL){
curr = curr->left;
}
//return the successor node
return node;
}

Node *deleteNode(Node *root, int val){
//base case
if(root==NULL){
return root;
}
    if (key < root->value){
// If the val to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    root->left = deleteNode(root->left, val); 
}else if (key > root->value){
// If the key to be deleted is greater than the root's key, 
    // then it lies in right subtree 
        root->right = deleteNode(root->right, val);
}else {
//if the val is the same as the node value then this is the node to be deleted
//if the node has only 1 child or no child
if(root->left==NULL){
Node *temp = root->right;
free(root);
return temp;
}else if(root->right==NULL){
Node *temp = root->left;
free(root);
return temp;
}
//if the node has 2 child then get the successor(the smallest node in the right subtree)
Node *temp = getSuccessor(root->right);
//copy the successor to the root
root->value = temp->value;
//delete the successor node
root->right = deleteNode(root->right, temp->value);
}
return root;
}


Comments

Post a Comment

Popular posts from this blog

Linked List Linked List a sequence of data structure connected together via links. In C a list is usually composed of multiple type of data so we usually use struct so that we can insert multiple amount of data into a single list, also our list also contain a reference(pointer in C) to the next list. So because of this reference our list linked to one another and that is also why this is called linked list. Also in linked list there is another reference that is Head and Tail . Head point to the first list in our linked list and Tail point to the last of our list in the linked list. Now Linked List usually have 2 type that is : 1. Single Linked List 2. Double/Doubly Linked List Single Linked List A single linked list have only one reference that is a reference to the next list. So we could think that a single linked list is like an array.  As seen a single linked list only contain one reference that point to the next list. Also in our tail the next poin...
Post a Comment
Read more
Stack & Queue Stack Stack is type of data structure that store it's data in an orderly manner. Data in stack can only be removed and added from one end of the data. This is called LIFO (Last in First Out) Meaning that the last data that enter will be the first one to be removed. Stack can be implemented with array or linked list. Stack is usually used in backtracking algorithm and also used when making a recursive function (Depth First Search). Queue Queue is also a type of data structure but it's main difference from stack is that in queue data can only be added from behind and data can only be removed from the front of the queue just like a real life queue. This is called FIFO (First In First Out) meaning that the first data that is inserted will be the one that is removed first. Also like stack queue can be implemented with array or linked list. Now queue is used in an algorithm called Breath First Search. Queue also have another type called Circular Que...
Post a Comment
Read more

AVL dan B-Tree

AVL TREE In Computer Science term an AVL tree is a type of self-balancing binary tree. The word AVL come from it's inventor  A delson- V elsky and  L andis. It's the first of such Data Structure. The term self-balancing mean that an AVL tree will maintain both of it's subtree height so that their height diffenrence will be 1, -1, or 0. This is called the balance facotr of an AVL tree. Basically an AVL tree is like an Binary Search Tree but with an self-balancing function built into it.  Why Use an AVL Tree The reasoning to why we must balance the tree if it's not balanced is so that the time complexity for the operation (Search, Insert, Delete) will always be at O(log n) instead of the usual O(h) (where h is the height of the tree ) for the worst case scenario.  Example of a skewed tree For the tree above say that we want to search for the node 74 that we have to traverse the entire tree to find said note but if it's an AVL tree then We on...
Post a Comment
Read more