Binary Search Trees
What is a binary search tree(BST):
- A binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure.
- To be a binary search tree first, the tree should satisfy all the properties of a binary tree.
- This binary search tree is a data structure for efficient searching, insertion, and deletion.
- Binary search tree properties:
- For every node X(root).
- All the keys in its left subtree are smaller than the key value in X(root).
- All the keys in its right subtree are larger than the key value in X(root).
- In the above figure, the left tree is a binary search tree, whereas the right tree is not a binary search tree as it doesn't satisfy the properties of BST.
Operations performed on BST:
- Searching.
- Insertion.
Searching BST
- If we are searching for a key that is equal to root, then we are done with searching.
- If we are searching for a key<root, then we must search in the left sub-tree.
- If we are searching for a key>root, then we must search in the right sub-tree.
Search for 10:
- Compare 10:5(root), as 10>5, go to right sub-tree.
- Compare 10:8, as 10>8, go to right sub-tree.
- Compare 10:9, as 10>9, go to the right sub-tree.
- Compare 10:11, as 10<11, go to left sub-tree.
- Compatre 10:10, 10=10, found it!.
Implementation of searching operation in c/c++:
bool search(struct node *root, int key)
{
if(root==NULL)//If the tree is empty
{
return false;
}
else if(key==root->data)//If the key is found at the root then return root.
{
return true;
}
else if(key < root->data)//If the key is less than the root node then search in left subtree.
{
return search(root->left,key);
}
else{
return search(root->right,key); //If the key is greater than the root node then search in right subtree.
}
}
Insertion in BST
- If the tree is empty(root==NULL), then consider the new element as root.
- If the element is greater than the root, then insert the element to right sub-tree.
- If the element is less than the root, then insert the element to left sub-tree.
Implementation of insertion operation in c/c++:
BST* Insert(BST* root,int data) {
if(root == NULL) // empty tree
{
root = AddNewNode(data);
}
else if(data <= root->data) // if data to be inserted is lesser, insert in left subtree.
{
root->left = Insert(root->left,data);
}
else // else, insert in right subtree.
{
root->right = Insert(root->right,data);
}
return root;
}
Binary search tree implementation:
// Binary Search Tree - Implemenation in C++
// Simple program to create a BST of integers and search an element in it
#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BST {
int data;
BST* left;
BST* right;
};
// Function to create a new Node in heap
BST* AddNewNode(int data) {
BST* newNode = new BST();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// To insert data in BST, returns address of root node
BST* Insert(BST* root,int data) {
if(root == NULL) { // empty tree
root = AddNewNode(data);
}
// if data to be inserted is lesser, insert in left subtree.
else if(data <= root->data) {
root->left = Insert(root->left,data);
}
// else, insert in right subtree.
else {
root->right = Insert(root->right,data);
}
return root;
}
//To search an element in BST, returns true if element is found
bool Search(BST* root,int data) {
if(root == NULL) {
return false;
}
else if(root->data == data) {
return true;
}
else if(data <= root->data) {
return Search(root->left,data);
}
else {
return Search(root->right,data);
}
}
int main() {
BST* root = NULL; // Creating an empty tree
root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,8);
root = Insert(root,12);
// Ask user to enter a number.
int number;
cout<<"Enter number be searched\n";
cin>>number;
//If number is found, print "FOUND"
if(Search(root,number) == true) cout<<"Found\n";
else cout<<"Not Found\n";
}
So, we have come to an end of this article. I hope you guys liked this article.
Here are some articles you people may like:
0 Comments