A height balanced binary tree, also known as an AVL tree, is a type of binary search tree that is designed to maintain a balance between the left and right subtrees. This balance is achieved by ensuring that the height difference between the left and right subtrees is not greater than 1. In this article, we will discuss the concept of height balanced binary trees and how to implement them in C++.
A binary search tree is a type of binary tree where the left subtree of a node contains only nodes with keys that are less than the node's key, and the right subtree of a node contains only nodes with keys that are greater than the node's key. This allows for efficient searching, insertion, and deletion operations. However, if the tree becomes unbalanced, the performance of these operations can degrade.
An AVL tree is a type of binary search tree that maintains balance by ensuring that the height difference between the left and right subtrees is not greater than 1. This is achieved through a process called rotation. Rotation is the process of moving a node and its subtrees to a different position in the tree. There are two types of rotations: left rotation and right rotation. A left rotation is performed when the right subtree of a node is taller than its left subtree. A right rotation is performed when the left subtree of a node is taller than its right subtree.
In order to implement an AVL tree in C++, we first need to define the structure of a node. The node structure should contain the key, the left and right pointers, and the height of the node. The height of the node is used to determine the balance of the tree.
struct Node { int key; struct Node *left; struct Node *right; int height; };
The next step is to implement the insertion operation. The insertion operation is similar to the insertion operation in a binary search tree. However, after inserting a new node, we need to check the balance of the tree and perform rotations if necessary.
// Insert a new node into the AVL tree struct Node* insert(struct Node* node, int key) { // Perform the standard BST insertion if (node == NULL) return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST return node;
// Update the height of the current node node->height = 1 + max(height(node->left),
height(node->right)); // Get the balance factor of this node to check whether
// this node became unbalanced int balance = getBalance(node); // If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case if (balance < -1 && key > node->right->key)
return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node); } // Right Left Case
if (balance < -1 && key < node->right->key node->right = rightRotate(node->right);
return leftRotate(node);
}// Return the (unchanged) node pointer
return node;
}
The next step is to implement the rotations. The leftRotate and rightRotate functions are used to perform the rotations. The leftRotate function is used when the right subtree of a node is taller than its left subtree, and the rightRotate function is used when the left subtree of a node is taller than its right subtree.
// A utility function to left rotate subtree rooted with x // See the diagram given above. struct Node *leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left;
// Perform rotation y->left = x;
x->right = T2; // Update heights x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Return new root
return y; }
// A utility function to right rotate subtree rooted with y // See the diagram given above. struct Node *rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right;
// Perform rotation x->right = y;
y->left = T2; // Update heights y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Return new root return x;
}
The final step is to implement the deletion operation. The deletion operation is similar to the deletion operation in a binary search tree. However, after deleting a node, we need to check the balance of the tree and perform rotations if necessary.
// A utility function to delete the node with the given key // from the AVL tree struct Node* deleteNode(struct Node* root, int key) { // Step 1 - Perform standard BST delete if (root == NULL) return root;
// If the key to be deleted is smaller than the
// root's key, then it lies in left subtree if ( key < root->key )
root->left = deleteNode(root->left, key); // If the key to be deleted is greater than the
// root's key, then it lies in right subtree else if( key > root->key )
root->right = deleteNode(root->right, key); // if key is same as root's key, then this is the node
// to be deleted else { // node with only one child or no child if( (root->left == NULL) ||
(root->right == NULL) ) { struct Node *temp = root->left ?
root->left :
root->right; // No child case if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of
// the non-null child free(temp); } else { // node with two children: Get the inorder // successor (smallest in the right subtree) struct Node* temp = minValueNode(root->right);
// Copy the inorder successor's data to this node
root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); }
} // If the tree had only one node then return if (root == NULL)
return root; // Step 2 - Update the height of the current node
root->height = 1 + max(height(root->left),
height(root->right)); // Step 3 - Get the balance factor of this node (to check whether
// this node became unbalanced)
int balance = getBalance(root); // If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root); }
// Right Right Case if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root); // Right Left Case
if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root;
}
In conclusion, an AVL tree is a type of binary search tree that maintains balance by ensuring that the height difference between the left and right subtrees is not greater than 1. It is implemented in C++ by defining the structure of a node, implementing the insertion, deletion and rotation operations, and checking the balance of the tree after each operation. By using an AVL tree, we can ensure that the performance of searching, inserting, and deleting operations remains optimal even when the tree becomes large.
