Bansilal Ramnath Agarwal Charitable Trust's
Vishwakarma Institute of Information Technology
Department of
Artificial Intelligence and Data Science
Name: Devkinandan Jagtap
Class: SY Division: A Roll No:271024
Semester: IV Academic Year: 2021-2022
Subject Name & Code: Advance Data Structure (ADUA22202)
Title of Assignment: Implement binary search tree and perform following
operations:-
a)Inserting into binary tree.
b)Searching binary tree.
c)Deletion from binary search tree.
Date of Performance: 27-01-2022 Date of Submission:01-02-2022
Aim: Implement binary search tree and perform following operations:-
a)Inserting into binary tree.
b)Searching binary tree.
c)Deletion from binary search tree.
Problem Statement: Implement binary search tree and perform following
operations:-
a)Inserting into binary tree.
b)Searching binary tree.
c)Deletion from binary search tree.
Background Information: Binary Search Tree is a node-based binary tree
data structure which has the following properties:
• The left subtree of a node contains only nodes with keys lesser than the
node’s key.
• The right subtree of a node contains only nodes with keys greater than
the node’s key.
• The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
Basic Operations:
Following are the basic operations of a tree −
• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Delete- Deletes an element from the tree.
1. Search
For searching a value, if we had a sorted array we could have performed a
binary search. Let’s say we want to search a number in the array, in binary
search, we first define the complete list as our search space, the number can
exist only within the search space. Now we compare the number to be
searched or the element to be searched with the middle element (median) of
the search space and if the record being searched is less than the middle
element, we go searching in the left half, else we go searching in the right
half, in case of equality we have found the element. In binary search we start
with ‘n’ elements in search space and if the mid element is not the element
that we are looking for, we reduce the search space to ‘n/2’ we keep
reducing the search space until we either find the record that we are looking
for or we get to only one element in search space and be done with this
whole reduction.
2. Insert
A new key is always inserted at the leaf. We start searching a key from the
root until we hit a leaf node. Once a leaf node is found, the new node is
added as a child of the leaf node.
3. Delete
When we delete a node, three possibilities arise.
1) Node to be deleted is the leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node
and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the
node. Copy contents of the inorder successor to the node and delete the
inorder successor. Note that inorder predecessor can also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
The important thing to note is, inorder successor is needed only when the
right child is not empty. In this particular case, inorder successor can be
obtained by finding the minimum value in the right child of the node.
Software Requirements: VS Code
Program Code:
#include<iostream>
using namespace std;
class BST{
struct node{
int data;
node* left;
node* right;
};
node* root;
node* makeEmpty(node* t){
if(t==NULL)
return NULL;
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
return NULL;
}
node* insert(int x, node* t){
if(t==NULL)
{
t=new node;
t->data=x;
t->left=t->right=NULL;
}
else if(x<t->data)
t->left=insert(x, t->left);
else if(x>t->data)
t->right=insert(x, t->right);
return t;
}
node* findMin(node* t){
if(t==NULL)
return NULL;
else if(t->left==NULL)
return t;
else
return findMin(t->left);
}
node* findMax(node* t){
if(t==NULL)
return NULL;
else if(t->right==NULL)
return t;
else
return findMax(t->right);
}
node* remove(int x, node* t){
node* temp;
if(t==NULL)
return NULL;
else if(x<t->data)
t->left=remove(x, t->left);
else if(x>t->data)
t->right=remove(x, t->right);
else if(t->left && t->right){
temp=findMin(t->right);
t->data=temp->data;
t->right=remove(t->data, t->right);
}
else
{
temp=t;
if(t->left==NULL)
t=t->right;
else if(t->right==NULL)
t=t->left;
delete temp;
}
return t;
}
void inorder(node* t){
if(t==NULL)
return;
inorder(t->left);
cout<<t->data<<" ";
inorder(t->right);
}
node* find(node* t, int x){
if(t==NULL)
return NULL;
else if(x<t->data)
return find(t->left,x);
else if(x>t->data)
return find(t->right,x);
else return t;
}
public:
BST(){
root=NULL;
}
~BST(){
root=makeEmpty(root);
}
void insert(int x){
root=insert(x,root);
}
void remove(int x){
root=remove(x,root);
}
void display(){
inorder(root);
cout<<endl;
}
void search(int x){
root=find(root,x);
}
};
int main(){
BST t;
t.insert(20);
t.insert(25);
t.insert(15);
t.insert(10);
t.insert(30);
t.insert(40);
t.display();
return 0;
}
Results or Experimentation:
Conclusion: From this assignment we can understood that how to perform
searching, insertion and deletion in binary search tree.
