Binary Search Trees in c++

 

Binary Search Trees (BSTs) are a type of data structure that allows for efficient searching, insertion, and deletion of elements. They are commonly used in computer science, particularly in the field of algorithms and data structures. In this article, we will be discussing the implementation and use of Binary Search Trees in the C++ programming language.

Binary Search Trees are a type of tree data structure where each node in the tree has at most two children. The left child of a node contains elements that are less than the parent node, while the right child contains elements that are greater than the parent node. This ordering of elements allows for efficient searching, as the search algorithm can repeatedly split the tree in half, narrowing down the search space until the desired element is found.

The basic structure of a BST node in C++ is as follows:

struct Node {
     
int data;
 Node* left;
 Node* right;
 };

The data field contains the value of the node, while the left and right fields point to the left and right children of the node, respectively.

Insertion into a BST is a recursive process that begins at the root of the tree. If the tree is empty, the new element is inserted as the root. Otherwise, the algorithm compares the value of the new element to the value of the current node. If the new element is less than the current node, the algorithm recursively calls itself on the left child. If the new element is greater than the current node, the algorithm recursively calls itself on the right child. If the current node is a leaf, the new element is inserted as a child of that node.

Here is an example of an insertion function in C++:

void insert(Node*& root, int value) {
     
if (root == nullptr) {
 root = new Node{value, nullptr, nullptr};
 return; 
 }
 if (value < root->data) {
 insert(root->left, value);
 }
 else 
{
 insert(root->right, value); 
 }
}

Searching for an element in a BST is also a recursive process that begins at the root of the tree. The algorithm compares the value of the desired element to the value of the current node. If the desired element is less than the current node, the algorithm recursively calls itself on the left child. If the desired element is greater than the current node, the algorithm recursively calls itself on the right child. If the desired element is equal to the value of the current node, the search is successful. If the current node is a leaf and the desired element is not found, the search is unsuccessful.

Here is an example of a search function in C++:

bool search(Node* root, int value) {
 if (root == nullptr) {
 return false;
 }
 if (value == root->data) {
 return true;
 }
     
if (value < root->data) {
 return search(root->left, value); 
 } 
else 
{
 return search(root->right, value);
 }
}

Deletion of an element from a BST is a bit more complex than insertion or searching. There are three cases to consider when deleting an element from a BST:

  1. The element to be deleted is a leaf node: In this case, the element can simply be removed from the tree by setting the parent's pointer to that element to

    nullptr. 2. The element to be deleted has one child: In this case, the parent's pointer to the element can be set to point to the element's child, effectively removing the element from the tree.

  2. The element to be deleted has two children: In this case, the element must be replaced with either its in-order predecessor or successor before it can be removed. The in-order predecessor is the largest element in the left subtree, while the in-order successor is the smallest element in the right subtree. Once the replacement element is found, it can be deleted as in cases 1 or 2.

Here is an example of a deletion function in C++:

void deleteNode(Node*& root, int value) {
 if (root == nullptr) {
 return;
 }
 if (value < root->data) {
 deleteNode(root->left, value);
 } 
else if (value > root->data) {
 deleteNode(root->right, value); 
 } 
else {
        if (root->left == nullptr) {
 Node* temp = root->right; 
 delete root; 
 root = temp; 
 }
 else if (root->right == nullptr) {
 Node* temp = root->left; 
 delete root;
 root = temp;
 } 
else {
            Node* temp = findMin(root->right);
 root->data = temp->data;
 deleteNode(root->right, temp->data);
 }
    }
}

Note that in this example, we are using a helper function called "findMin" to find the in-order successor of the element to be deleted. This function simply recursively traverses the left subtree of a node until it reaches a leaf node.

Binary Search Trees are a powerful and efficient data structure for searching, insertion, and deletion of elements. They can be used in a wide range of applications, from sorting algorithms to databases. By understanding the implementation and use of BSTs in C++, you can add this useful tool to your programming arsenal.

 

Binary Search Trees in c++

csadda

Posted by csadda