🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
An AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing binary search tree where the difference between the heights of the left and right subtrees (the balance factor) of every node is either -1, 0, or 1. It ensures O(log n) time complexity for search, insert, and delete operations. This blog post provides a detailed C++ implementation of an AVL tree, offering insight into the balancing mechanisms.
2. Program Overview
The program will:
1. Implement an AVL tree with methods to:
- Insert nodes.
- Delete nodes.
- Display the tree (in-order traversal).
- Search
2. Ensure that the tree remains balanced after each insertion or deletion.
3. Showcase the tree's self-balancing properties with a sample driver program.
3. Code Program
#include <iostream>
using namespace std;
class Node {
public:
int key, height;
Node* left;
Node* right;
Node(int k) {
key = k;
height = 1;
left = nullptr;
right = nullptr;
}
};
class AVLTree {
public:
Node* root;
AVLTree() : root(nullptr) {}
int height(Node* n) {
return n ? n->height : 0;
}
int getBalance(Node* n) {
return n ? height(n->left) - height(n->right) : 0;
}
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;
}
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key < node->key) node->left = insert(node->left, key);
else if (key > node->key) node->right = insert(node->right, key);
else return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key) return rightRotate(node);
if (balance < -1 && key > node->right->key) return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current->left) current = current->left;
return current;
}
Node* deleteNode(Node* root, int key) {
if (!root) 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 || !root->right) {
Node* temp = root->left ? root->left : root->right;
if (!temp) {
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) return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
if (balance > 1) {
if (getBalance(root->left) >= 0) return rightRotate(root);
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1) {
if (getBalance(root->right) <= 0) return leftRotate(root);
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
};
int main() {
AVLTree tree;
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
cout << "Inorder traversal of the AVL tree is: ";
tree.inorder(tree.root);
cout << endl;
tree.root = tree.deleteNode(tree.root, 20);
cout << "Inorder traversal after deleting 20: ";
tree.inorder(tree.root);
cout << endl;
return 0;
}
Output:
Inorder traversal of the AVL tree is: 10 20 25 30 40 50 Inorder traversal after deleting 20: 10 25 30 40 50
4. Step By Step Explanation
1. Each node of the AVL tree holds a key, pointers to its left and right children, and its height.
2. The AVLTree class contains methods for node insertion and rotation operations.
3. Node insertion in an AVL tree follows the regular Binary Search Tree (BST) insertion, with the addition of rotations (left, right, left-right, and right-left) to balance the tree if the balance factor becomes less than -1 or greater than 1.
4. The getBalance function determines if a given node is left-heavy or right-heavy.
5. The rightRotate and leftRotate functions help in balancing skewed subtrees.
6. minValueNode function returns the node with the smallest key value in the AVL tree.
7. deleteNode is the AVL tree deletion function. It first performs the standard BST delete and then ensures the AVL tree properties are maintained.
8. The search function checks if a given key is present in the AVL tree.
9. The inorder function prints an inorder traversal of the AVL tree, which will display the tree's nodes in sorted order.
10. The main function demonstrates the insertion of nodes, an inorder traversal, and deletion from the AVL tree.
The provided comments in the code further explain each segment of the AVL tree implementation.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment