Software Developer
A binary search tree in C++ is defined as a data shape that consists of the node-primarily based binary tree where each node consists of at most 2 nodes that are called infant nodes. This tree is also called an ordered or sorted tree. The usage of this idea, you may store numbers in an organized way and a binary tree helps in a quick search, upload, and/or delete operations to be executed on the dataset. Using the idea you possibly can implement dynamic sets and research tables. The shape of the binary tree permits skipping of half of the final tree accordingly leading to higher time complexity with the average being o(log n) for seek, upload, and/or delete operations. This technique is higher than the linear search due to its improved time complexity. In this newsletter, we will examine all of the standards of addition, seek and delete in the first-rate element.
Retrieve the value of root in a Binary Search tree:
root->key
Point to the left of the root in a Binary Search tree:
root->left
Point to the right of the root in a Binary Search tree:
root->right
By now we understand that the Binary Search tree (BST) has a root node and at max 2 child nodes either on to left or right or both. The algorithm in a BST undergoes operations by comparison of values in the root node, and subsequently, it is lesser or more, the navigation in the tree takes place accordingly. In the working of Binary search tree, 3 operations are performed, namely:
With the understanding of the above 3 processes, it will be easier to now look at some examples, to get the practical experience of the theory we just learned.
Here are the following examples mentioned below:
Insert in Binary Search Tree in C++
#include <iostream>
using namespace std;
class nodeBST
{
int key;
nodeBST *lft, *rgt;
public:
nodeBST();
nodeBST(int);
nodeBST* insertFunc(nodeBST*, int);
void traverseInOrder(nodeBST*);
};
nodeBST ::nodeBST()
: key(0)
, lft(NULL)
, rgt(NULL)
{
}
nodeBST ::nodeBST(int value)
{
key = value;
lft = rgt = NULL;
}
nodeBST* nodeBST ::insertFunc(nodeBST* root, int value)
{
if (!root)
{
return new nodeBST(value);
}
if (value > root->key)
{
root->rgt = insertFunc(root->rgt, value);
}
else
{
root->lft = insertFunc(root->lft, value);
}
return root;
}
void nodeBST ::traverseInOrder(nodeBST* root)
{
if (!root) {
return;
}
traverseInOrder(root->lft);
cout << root->key << endl;
traverseInOrder(root->rgt);
}
int main()
{
nodeBST node, *root = NULL;
root = node.insertFunc(root, 0);
node.insertFunc(root, 27);
node.insertFunc(root, 9);
node.insertFunc(root, 19);
node.insertFunc(root, 91);
node.insertFunc(root, 2);
node.insertFunc(root, 7);
cout<<"\nThe sorted binary search tree is "<< endl;
node.traverseInOrder(root);
return 0;
}
Search in Binary Search Tree in C++.
#include <iostream>
using namespace std;
class nodeBST
{
public:
int key;
nodeBST *lft, *rgt;
nodeBST();
nodeBST(int);
nodeBST* insertFunc(nodeBST*, int);
nodeBST* searchFunc(nodeBST*, int);
void traverseInOrder(nodeBST*);
};
nodeBST ::nodeBST()
: key(0)
, lft(NULL)
, rgt(NULL)
{
}
nodeBST ::nodeBST(int value)
{
key = value;
lft = rgt = NULL;
}
nodeBST* nodeBST ::insertFunc(nodeBST* root, int value)
{
if (!root)
{
return new nodeBST(value);
}
if (value > root->key)
{
root->rgt = insertFunc(root->rgt, value);
}
else
{
root->lft = insertFunc(root->lft, value);
}
return root;
}
nodeBST* nodeBST ::searchFunc(nodeBST* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return searchFunc(root->rgt, key);
return searchFunc(root->lft, key);
}
void nodeBST ::traverseInOrder(nodeBST* root)
{
if (!root) {
return;
}
traverseInOrder(root->lft);
cout << root->key << endl;
traverseInOrder(root->rgt);
}
int main()
{
nodeBST node, *root = NULL, *searchRoot = NULL;
root = node.insertFunc(root, 0);
node.insertFunc(root, 27);
node.insertFunc(root, 9);
node.insertFunc(root, 19);
node.insertFunc(root, 91);
node.insertFunc(root, 2);
node.insertFunc(root, 7);
cout<<"\nThe sorted binary search tree is "<< endl;
node.traverseInOrder(root);
cout<<"\nSearch for 7 in the BST "<< endl;
searchRoot = node.searchFunc(root, 7);
if(searchRoot == NULL)
{
cout<<"Value Not Found\n";
}
else
{
cout << "Value Found! "<<searchRoot->key<<"\n";
}
cout<<"\nSearch for 2709 in the BST "<< endl;
*searchRoot = NULL;
searchRoot = node.searchFunc(root, 2709);
if(searchRoot == NULL)
{
cout<<"Value Not Found\n";
}
else
{
cout << "Value Found! "<<searchRoot->key<<"\n";
}
return 0;
}
Delete in Binary Search Tree in C++.
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
struct node *lft, *rgt;
};
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->lft = temp->rgt = NULL;
return temp;
}
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->lft);
cout << root->key << " ";
inorder(root->rgt);
}
}
struct node* insertFunc(struct node* node, int val)
{
if (!node)
{
return newNode(val);
}
if (val > node->key)
{
node->rgt = insertFunc(node->rgt, val);
}
else
{
node->lft = insertFunc(node->lft, val);
}
return node;
}
struct node* minValueNode(struct node* node)
{
struct node* current = node;
while (current && current->lft != NULL)
current = current->lft;
return current;
}
struct node* deleteFunc(struct node* root, int key)
{
if (root == NULL)
return root;
if (key < root->key)
root->lft = deleteFunc(root->lft, key);
else if (key > root->key)
root->rgt = deleteFunc(root->rgt, key);
else {
if (root->lft==NULL and root->rgt==NULL)
return NULL;
else if (root->lft == NULL) {
struct node* temp = root->rgt;
free(root);
return temp;
}
else if (root->rgt == NULL) {
struct node* temp = root->lft;
free(root);
return temp;
}
struct node* temp = minValueNode(root->rgt);
root->key = temp->key;
root->rgt = deleteFunc(root->rgt, temp->key);
}
return root;
}
int main()
{
struct node* root = NULL;
root = insertFunc(root, 27);
root = insertFunc(root, 9);
root = insertFunc(root, 19);
root = insertFunc(root, 91);
root = insertFunc(root, 2);
root = insertFunc(root, 7);
root = insertFunc(root, 0);
root = insertFunc(root, 1);
cout << "Inorder traversal of the given tree \n";
inorder(root);
cout << "\n<Delete> 1\n";
root = deleteFunc(root, 1);
cout << "Traversing the modified tree \n";
inorder(root);
cout << "\n<Delete> 19\n";
root = deleteFunc(root, 19);
cout << " Traversing the modified tree \n";
inorder(root);
cout << "\n<Insert> 72\n";
root = insertFunc(root, 72);
cout << " Traversing the modified tree \n";
inorder(root);
cout << "\n<Delete> 7\n";
root = deleteFunc(root, 7);
cout << " Traversing the modified tree \n";
inorder(root);
return 0;
}