Binary Search Tree Program in C++
A binary search tree is defined in C++ as a node-based binary tree data structure in which each node has a maximum of two child nodes. This tree also goes by names such as ordered tree and sorted tree. With this concept, numbers can be stored orderly, and the binary tree makes quick searches, additions, and data deletions on the dataset possible.
The theory behind them can be used to construct dynamic sets and lookup tables. Which has an average time complexity of O (log n) for operations like Search, add, and delete; the binary tree's structure allows for the skip of over half of the remaining tree.
How does the Binary Search Tree in C++ Function?
The Binary Search tree (BST) should now be understood to have a root node and a maximum of two child nodes, which may be on the left, right, or both. The navigation in the tree is then done according to whether the values of the root node are less or more when the algorithm in a BST compares them.
Basic Operations on Binary Search Tree
1. Insertion:
A new node is inserted into a Binary Search Tree (BST) by being assigned the appropriate position based on its value. The new node becomes the Root if the tree is empty. If not, it moves left for lower values or is suitable for larger values until it reaches space, comparing values as it moves through the tree. The activity guarantees the upkeep of the BST property. The worst-case time complexity for skewed trees is O(n), with an average of O (log n).
2. Search:
The process of searching in a Binary Search Tree (BST) is comparing the desired value with the current node and then moving left or right in response to the comparison (BST). This procedure continues until the value is located or the Search reaches a null node. The typical time complexity for skewed trees is O(log n), but it can be O(n) in the worst case. Searching in BSTs is made effective by balancing strategies.
3. Deletion:
Before removing a value from the BST, the algorithm uses the Search mentioned above operation to locate the node that contains it. Depending on the node's children, the deletion procedure can change after it is located:
1. The leaf node in the first instance is the node that must be eliminated. Remove the node from the tree in this scenario.
2. The node that needs to be eliminated in this scenario has just one child node. In this situation, take the following actions:
- Put its child node in its place.
- The child node should be removed from its initial location.
3. In the third scenario, the node that should be eliminated has two offspring. In this situation, take the following actions:
- Obtain that node's in-order successor.
- Put the in-order successor in place of the node.
- The in-order successor should be removed from its initial location.
A BST maintains its properties by carrying out these actions, keeping its elements organized in an order that makes efficient searching, insertion, and deletion possible with, on average, logarithmic time complexity.
4. Traversal:
We can explore and process nodes in a particular order by performing traversals in Binary Search Trees (BST). Each node in a BST has a maximum of two children, and its left subtree only consists of nodes with keys less than the node's key, while its right subtree only consists of nodes with keys more significant than the node's key. Inorder, Preorder, and Postorder traversals are the three primary traversals in a BST.
Nodes in a Binary Search Tree (BST) are visited in the following order during an inorder traversal:
- Traverse through the left subtree.
- Visit the current node.
- Explore (traverse) the right subtree.
This traversal creates nodes in an ordered BST arranged according to their keys in ascending order. It produces a sorted series of elements, in other words.
Preorder Traversal: Nodes in a BST are visited in the following order during a preorder.
- Visit the current node.
- Traverse the left subtree.
- Explore(traverse) the right subtree.
Preorder traversal is frequently used to duplicate a tree structure or serialize a tree into a series.
Postorder Traversal: Nodes in a BST are visited in the following order during a postorder traversal:
- Traverse the left subtree.
- Explore(traverse) the right subtree.
- Visit the current node.
Postorder traversal is typically used when carrying out calculations that call for processing child nodes before the parent node or when removing the entire tree.
Example:
Let's see the program performing all operations in the binary search tree:
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node
{
int data;
struct Node *left;
struct Node *right;
} *root;
class BST
{
Public:
void search(Node *, int);
void find(int, Node **, Node **);
void insert(Node *, Node *);
void remove(int);
void removeCaseA(Node *, Node *);
void removeCaseB(Node *, Node *);
void removeCaseC(Node *, Node *);
void preOrder(Node *);
void inOrder(Node *);
void postOrder(Node *);
void display(Node *, int);
BST()
{
root = NULL;
}
};
void BST::find(int value, Node **parent, Node **location)
{
Node *ptr, *ptrSave;
if (root == NULL)
{
*location = NULL;
*parent = NULL;
return;
}
if (value == root->data)
{
*location = root;
*parent = NULL;
return;
}
if (value < root->data)
ptr = root->left;
else
ptr = root->right;
ptrSave = root;
while (ptr != NULL)
{
if (value == ptr->data)
{
*location = ptr;
*parent = ptrSave;
return;
}
ptrSave = ptr;
if (value < ptr->data)
ptr = ptr->left;
else
ptr = ptr->right;
}
*location = NULL;
*parent = ptrSave;
}
void BST::search(Node *root, int data)
{
int depth = 0;
Node *temp = root;
while (temp != NULL)
{
depth++;
if (temp->data == data)
{
cout << "\nData found at depth: " << depth << endl;
return;
}
else if (temp->data > data)
temp = temp->left;
else
temp = temp->right;
}
cout << "\nData not found" << endl;
return;
}
void BST::insert(Node *tree, Node *newNode)
{
if (root == NULL)
{
root = new Node;
root->data = newNode->data;
root->left = NULL;
root->right = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (tree->data == newNode->data)
{
cout << "Element already in the tree" << endl;
return;
}
if (tree->data > newNode->data)
{
if (tree->left != NULL)
{
insert(tree->left, newNode);
}
else
{
tree->left = new Node;
tree->left->data = newNode->data;
tree->left->left = NULL;
tree->left->right = NULL;
cout << "Node Added To Left" << endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newNode);
}
else
{
tree->right = new Node;
tree->right->data = newNode->data;
tree->right->left = NULL;
tree->right->right = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
void BST::remove(int value)
{
Node *parent, *location;
if (root == NULL)
{
cout << "Tree empty" << endl;
return;
}
find(value, &parent, &location);
if (location == NULL)
{
cout << "Item not present in the tree" << endl;
return;
}
if (location->left == NULL && location->right == NULL)
{
removeCaseA(parent, location);
cout << "Item deleted" << endl;
}
if (location->left != NULL && location->right == NULL)
{
removeCaseB(parent, location);
cout << "Item deleted" << endl;
}
if (location->left == NULL && location->right != NULL)
{
removeCaseB(parent, location);
cout << "Item deleted" << endl;
}
if (location->left != NULL && location->right != NULL)
{
removeCaseC(parent, location);
cout << "Item deleted" << endl;
}
free(location);
}
void BST::removeCaseA(Node *parent, Node *location)
{
if (parent == NULL)
{
root = NULL;
}
else
{
if (location == parent->left)
parent->left = NULL;
else
parent->right = NULL;
}
}
void BST::removeCaseB(Node *parent, Node *location)
{
Node *child;
if (location->left != NULL)
child = location->left;
else
child = location->right;
if (parent == NULL)
{
root = child;
}
else
{
if (location == parent->left)
parent->left = child;
else
parent->right = child;
}
}
void BST::removeCaseC(Node *parent, Node *location)
{
Node *ptr, *ptrSave, *successor, *parentSuccessor;
ptrSave = location;
ptr = location->right;
while (ptr->left != NULL)
{
ptrSave = ptr;
ptr = ptr->left;
}
successor = ptr;
parentSuccessor = ptrSave;
if (successor->left == NULL && successor->right == NULL)
removeCaseA(parentSuccessor, successor);
else
removeCaseB(parentSuccessor, successor);
if (parent == NULL)
{
root = successor;
}
else
{
if (location == parent->left)
parent->left = successor;
else
parent->right = successor;
}
successor->left = location->left;
successor->right = location->right;
}
void BST::preOrder(Node *ptr)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL)
{
cout << ptr->data << " ";
preOrder(ptr->left);
preOrder(ptr->right);
}
}
void BST::inOrder(Node *ptr)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL)
{
inOrder(ptr->left);
cout << ptr->data << " ";
inOrder(ptr->right);
}
}
void BST::postOrder(Node *ptr)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL)
{
postOrder(ptr->left);
postOrder(ptr->right);
cout << ptr->data << " ";
}
}
void BST::display(Node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level + 1);
cout << endl;
if (ptr == root)
cout << "Root: ";
else
{
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->data;
display(ptr->left, level + 1);
}
}
int main()
{
int choice, num;
BST bst;
Node *newNode;
while (true)
{
Cout << "1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. Display 8. Quit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
Case 1:
newNode = new Node;
cout << "Enter the number to be inserted: ";
cin >> newNode->data;
bst.insert(root, newNode);
break;
Case 2:
if (root == NULL)
{
cout << "Tree is empty, nothing to delete" << endl;
continue;
}
cout << "Enter the number to be deleted: ";
cin >> num;
bst.remove(num);
break;
case 3:
cout << "Search: ";
cin >> num;
bst.search(root, num);
break;
Case 4:
cout << "Inorder: ";
bst.inOrder(root);
cout << endl;
break;
Case 5:
cout << "Preorder: ";
bst.preOrder(root);
cout << endl;
break;
case 6:
cout << "Postorder: ";
bst.postOrder(root);
cout << endl;
break;
Case 7:
cout << "Display: ";
bst.display(root, 1);
cout << endl;
break;
Case 8:
exit(0);
Default:
cout << "Invalid choice" << endl;
}
}
return 0;
}
Output:
![Binary Search Tree Program in C++](https://static.tutorialandexample.com/cpp/binary-search-tree-program-in-cpp1.png)
Advantages of Binary Search Tree
- Effective Searching: For the insertion, deletion, and retrieval of elements, Binary Search Trees offer effective searching operations that take an average time complexity of O(log n). They are, therefore, appropriate for jobs that frequently require data retrieval and modification.
- Ordered data storage: A node's value must be more significant than all the values in its left subtree and smaller than all the values in its right subtree for BSTs to maintain an ordered arrangement of elements. When printing elements in ascending or descending order, for example, this ordering makes it simple to get the elements in sorted order.
- Dynamic Data Structure: BSTs can dynamically change their structure to add or delete components. Because of this, they are excellent choices for situations in which it is necessary to manage data effectively while a program is being run.
- Fast Insertion and Deletion: Inserting and removing components from a BST typically involves vertically traversing the tree and executing straightforward pointer operations. These operations often have an O(log n) average time complexity, which makes them quicker than operations on data structures like arrays or linked lists.
While not a characteristic of all BSTs, balanced BSTs (such as AVL trees or Red-Black trees) guarantee that the tree maintains its balance, preventing worst-case scenarios where it degenerates and turns into a linked list. This tree guarantees that various operations operate consistently in O(log n).
Conclusion
C++'s Binary Search Trees (BSTs) provide effective searching, organized data storage, and dynamic adaptation. They excel at operations with logarithmic time complexity, such as insertion, deletion, and retrieval.
Their popularity is further increased by features like memory efficiency, personalized comparators, and flexibility in integrating various data structures. To prevent this, the balance must be preserved. BSTs are crucial in computer science, offering efficient software solutions and optimized algorithms.