Binary Search Trees (BSTs) are a popular data structure used for efficient searching and sorting of data. However, if not implemented correctly, a BST can become unbalanced, leading to poor performance. One way to fix an unbalanced BST is to recover it using a process called tree rotation. In this article, we will discuss how to recover a BST in C++ using the tree rotation method.
A BST is a tree-based data structure in which each node has at most two children, left and right. The left child of a node is always less than the parent node, and the right child is always greater. This property is known as the BST property. The root node of a BST is the node with the smallest value, and the leaves are the nodes with no children.
A balanced BST is one in which the height of the tree is roughly the same for all nodes, leading to efficient searching and sorting. However, if a BST becomes unbalanced, the height of the tree can become skewed, leading to poor performance. This can happen if a node is inserted or deleted in such a way that the tree becomes unbalanced.
To recover a BST, we can use a technique called tree rotation. Tree rotation is a process in which we rotate the nodes of the tree to balance it. There are two types of tree rotations: left rotation and right rotation.
A left rotation is performed when the right subtree of a node is taller than the left subtree. In this case, we rotate the right subtree up to become the new root of the subtree. The left subtree of the right subtree becomes the right subtree of the new root, and the original root becomes the left subtree of the new root.
A right rotation is performed when the left subtree of a node is taller than the right subtree. In this case, we rotate the left subtree up to become the new root of the subtree. The right subtree of the left subtree becomes the left subtree of the new root, and the original root becomes the right subtree of the new root.
To implement tree rotation in C++, we first need to define the structure of our BST node. A typical BST node structure includes the value of the node, a pointer to the left child, and a pointer to the right child.
struct Node { int value; Node *left; Node *right; };
Next, we need to implement the functions for left and right rotation. The left rotation function takes a pointer to the node to be rotated as its argument. The function first checks if the right child of the node is not null. If it is not null, we assign the right child to be the new root of the subtree, and the left child of the right child becomes the right child of the original root. The original root becomes the left child of the new root.
void leftRotate(Node *&node) { if (node->right != NULL) { Node *newRoot = node->right; node->right = newRoot->left; newRoot->left = node; node = newRoot; } }
The right rotation function is similar to the left rotation function, but it rotates the left child up to become the new root of the subtree. The right child of the left child becomes the left child of the original root, and the original root becomes the right child of the new root.
void rightRotate(Node *&node) { if (node->left != NULL) { Node *newRoot
= node->left; node->left = newRoot->right; newRoot->right = node; node = newRoot; } }
To recover a BST using tree rotation, we can implement a function that checks the balance of the tree and performs the appropriate rotations. A common method to check the balance of a tree is to use the height of the left and right subtrees. If the difference in height between the left and right subtrees is greater than 1, then the tree is unbalanced and needs to be rotated.
int getBalance(Node *node) { if (node == NULL) return 0; return getHeight(node->left) - getHeight(node->right); }
int getHeight(Node *node) { if (node == NULL) return 0; return max(getHeight(node->left), getHeight(node->right)) + 1; }
void recoverBST(Node *&node) { int balance = getBalance(node); if (balance > 1) { if (getBalance(node->left) < 0) leftRotate(node->left); rightRotate(node); } else if (balance < -1) { if (getBalance(node->right) > 0) rightRotate(node->right); leftRotate(node); } }
It is important to note that tree rotation is not a one-time solution to unbalancing a BST. It needs to be performed recursively on all the nodes of the tree to ensure that the entire tree is balanced. This can be achieved by calling the recoverBST function on the left and right children of the current node after performing the rotation.
In addition, it is important to keep in mind that tree rotation only works for unbalanced trees. If a tree is already balanced, performing tree rotation will only make it worse. Therefore, it is important to implement a mechanism to check if the tree is already balanced before performing the rotation.
In conclusion, recovering a BST in C++ using tree rotation is an efficient method to balance an unbalanced tree. By implementing the appropriate rotations and recursively checking the balance of the tree, we can restore the efficiency of the BST and improve its performance. With the right implementation, a BST can be an effective data structure for searching and sorting data.
