AVL Tree Insertion and Deletion in C++
An AVL tree is a self-balancing binary search tree that ensures a balanced structure by performing rotations whenever an insertion or deletion operation might cause an imbalance. This balance ensures efficient search, insertion, and deletion operations with a time complexity of O(log n), where n is the number of nodes in the tree.
This article will provide a detailed explanation of AVL tree insertion and deletion operations in C++, along with a comprehensive code implementation.
AVL Tree Implementation in C++
Here's a C++ implementation of an AVL tree, including insertion and deletion methods:
#include
#include
using namespace std;
struct Node {
int data;
int height;
Node *left;
Node *right;
Node(int data) {
this->data = data;
this->height = 1;
this->left = nullptr;
this->right = nullptr;
}
};
// Function to get the height of a node
int getHeight(Node *node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
// Function to calculate the balance factor of a node
int getBalanceFactor(Node *node) {
if (node == nullptr) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
// Function to update the height of a node
void updateHeight(Node *node) {
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
}
// Function to perform a right rotation
Node *rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
updateHeight(y);
updateHeight(x);
// Return the new root
return x;
}
// Function to perform a left rotation
Node *leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
updateHeight(x);
updateHeight(y);
// Return the new root
return y;
}
// Function to insert a node into the AVL tree
Node *insert(Node *node, int data) {
if (node == nullptr) {
return new Node(data);
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
} else {
return node; // Duplicate data
}
// Update height
updateHeight(node);
// Calculate balance factor
int balance = getBalanceFactor(node);
// Perform rotations if necessary
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// Function to find the node with the minimum value in a subtree
Node *minValueNode(Node *node) {
Node *current = node;
while (current->left != nullptr) {
current = current->left;
}
return current;
}
// Function to delete a node from the AVL tree
Node *deleteNode(Node *root, int data) {
if (root == nullptr) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Node with only one child or no child
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 with two children
Node *temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
// If the tree had only one node
if (root == nullptr) {
return root;
}
// Update height
updateHeight(root);
// Calculate balance factor
int balance = getBalanceFactor(root);
// Perform rotations if necessary
if (balance > 1 && getBalanceFactor(root->left) >= 0) {
return rightRotate(root);
}
if (balance > 1 && getBalanceFactor(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalanceFactor(root->right) <= 0) {
return leftRotate(root);
}
if (balance < -1 && getBalanceFactor(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Function to print the AVL tree in preorder
void preorder(Node *root) {
if (root != nullptr) {
cout << root->data << " ";
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: ";
preorder(root);
cout << endl;
root = deleteNode(root, 20);
cout << "Preorder traversal after deleting 20: ";
preorder(root);
cout << endl;
return 0;
}
Explanation:
-
Node Structure: The
Nodestruct represents a node in the AVL tree, containing data, height, and pointers to its left and right children. -
Height Calculation:
getHeight()returns the height of a node, which is the number of edges on the longest path from the node to a leaf. -
Balance Factor Calculation:
getBalanceFactor()calculates the difference in height between the left and right subtrees of a node. A balance factor of 0 indicates a balanced node, while a positive or negative balance factor indicates an imbalance. -
Height Update:
updateHeight()updates the height of a node based on the heights of its children. -
Rotation Operations:
rightRotate()performs a right rotation around a given node.leftRotate()performs a left rotation around a given node.
-
Insertion:
insert()inserts a new node into the tree and maintains balance by performing rotations if necessary. -
Deletion:
deleteNode()deletes a node from the tree and maintains balance by performing rotations if necessary.- The function uses the
minValueNode()helper function to find the node with the minimum value in a subtree.
- The function uses the
-
Preorder Traversal:
preorder()performs a preorder traversal of the AVL tree.
Output:
Preorder traversal of the constructed AVL tree: 10 20 25 30 40 50
Preorder traversal after deleting 20: 10 25 30 40 50
This code demonstrates the basic principles of AVL tree insertion and deletion in C++. You can modify and expand it based on your specific needs and data structure requirements.