Introduction
AVL Trees are a type of self-balancing binary search tree, named after their inventors Adelson-Velsky and Landis. In this article, we will learn to write a C++ Program to Implement AVL Tree with detailed explanations and examples. AVL Trees are essential for maintaining balanced tree structures, ensuring efficient insertion, deletion, and lookup operations. By the end of this article, you will have a solid understanding of how to implement and use AVL Trees in your C++ projects.
Prerequisites
Before diving into the implementation of AVL Trees, it is important to have a basic understanding of the following concepts:
- Binary Search Trees (BSTs): A tree data structure where each node has at most two children referred to as the left child and the right child.
- Self-Balancing Trees: Trees that automatically keep their height (the longest path from the root to a leaf) small in the face of arbitrary sequences of insertions and deletions.
- C++ Standard Template Library (STL): Familiarity with basic STL components such as classes, templates, and pointers.
Make sure you are comfortable with these concepts to fully grasp the AVL Tree implementation.
1. Understanding AVL Trees
1.1 Properties of AVL Trees
An AVL Tree is a self-balancing binary search tree with the following properties:
- The heights of the two child subtrees of any node differ by at most one.
- Every node maintains a balance factor, which is the difference between the heights of its left and right subtrees. This factor must be -1, 0, or 1 for the tree to be balanced.
1.2 Why Use AVL Trees?
AVL Trees ensure that the tree remains balanced after each insertion and deletion operation, guaranteeing O(log n) time complexity for search, insertion, and deletion operations. This efficiency makes them suitable for applications where frequent insertions and deletions occur, such as databases and file systems.
2. Implementing AVL Tree in C++
Let’s go through three different examples to understand the implementation and usage of AVL Trees in C++.
2.1 Basic Implementation
In this example, we will implement the basic structure of an AVL Tree with insertion functionality.
Code
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left, *right;
int height;
};
int height(Node *N) {
return (N == nullptr) ? 0 : N->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = node->right = nullptr;
node->height = 1; // new node is initially added at leaf
return node;
}
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
int getBalance(Node* N) {
return (N == nullptr) ? 0 : height(N->left) - height(N->right);
}
Node* insert(Node* node, int key) {
if (node == nullptr)
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;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// 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 node;
}
void preOrder(Node *root) {
if (root != nullptr) {
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
int main() {
Node *root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
cout << "Preorder traversal of the constructed AVL tree is \n";
preOrder(root);
return 0;
}
Output
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
Explanation
In this example, we implement the basic structure of an AVL Tree with insertion functionality. The code includes functions for left and right rotations, calculating balance factors, and inserting nodes while maintaining the AVL Tree properties. The output shows the preorder traversal of the constructed AVL tree, demonstrating the balanced structure of the tree.
2.2 Deletion in AVL Tree
Next, we will extend our implementation to include deletion functionality.
Code
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left, *right;
int height;
};
int height(Node *N) {
return (N == nullptr) ? 0 : N->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = node->right = nullptr;
node->height = 1; // new node is initially added at leaf
return node;
}
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
int getBalance(Node* N) {
return (N == nullptr) ? 0 : height(N->left) - height(N->right);
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current->left != nullptr)
current = current->left;
return current;
}
Node* insert(Node* node, int key) {
if (node == nullptr)
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;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// 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 node;
}
Node* deleteNode(Node* root, int key) {
if (root == nullptr)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if ((root->left == nullptr) || (root->right == nullptr)) {
Node *temp = root->left ? root->left : root->right;
if (temp == nullptr) {
temp = root;
root = nullptr;
} else
*root = *temp;
delete temp;
} else {
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == nullptr)
return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
// 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;
}
void preOrder(Node *root) {
if (root != nullptr) {
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
int main() {
Node *root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
cout << "Preorder traversal of the constructed AVL tree is \n";
preOrder(root);
root = deleteNode(root, 10);
cout << "\nPreorder traversal after deletion of 10 \n";
preOrder(root);
return 0;
}
Output
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
Preorder traversal after deletion of 10
30 20 25 40 50
Explanation
In this example, we extend the AVL Tree implementation to include deletion functionality. The code ensures that the tree remains balanced after deletions, following the AVL Tree properties. The output shows the preorder traversal of the tree before and after the deletion of a node.
2.3 Real-World Application: Maintaining a Sorted List
In this example, we will use an AVL Tree to maintain a sorted list of integers and demonstrate how it can be used to efficiently insert and delete elements while keeping the list sorted.
Code
#include <iostream>
#include <set>
using namespace std;
class SortedList {
private:
set<int> avlTree;
public:
void insert(int data) {
avlTree.insert(data);
}
void deleteNode(int data) {
avlTree.erase(data);
}
void display() {
for (int item : avlTree) {
cout << item << " ";
}
cout << endl;
}
};
int main() {
SortedList list;
list.insert(10);
list.insert(20);
list.insert(15);
list.display();
list.deleteNode(20);
list.display();
return 0;
}
Output
10 15 20
10 15
Explanation
In this real-world example, we use the STL set class, which internally uses an AVL Tree to maintain the elements in a sorted order. The output shows how the list is maintained in a sorted order after each insertion and deletion operation.
Conclusion
AVL Trees are a powerful data structure that ensures balanced binary search trees, providing efficient operations for search, insertion, and deletion. Understanding and implementing AVL Trees in C++ can significantly enhance the performance of your applications that require sorted data structures. By following the examples provided in this article, you should now have a solid foundation for implementing and utilizing AVL Trees in your projects