Index
AVL Trees
AVL trees are a type of self-balancing binary search tree named after their inventors, Adelson-Velsky and Landis. They were the first such data structure to be invented and maintain balance during insertions and deletions.
Properties of AVL Trees:
- Balanced Height: An AVL tree is balanced if the heights of the left and right subtrees of every node differ by at most 1.
- Binary Search Tree Property: In addition to being balanced, an AVL tree must also maintain the binary search tree property, where the left subtree of a node contains only nodes with values less than the node’s value, and the right subtree contains only nodes with values greater than the node’s value.
Balancing Operations:
To maintain the balance property, AVL trees perform rotations when necessary during insertions and deletions. There are four types of rotations:
- Left Rotation: Rebalances the tree by rotating nodes to the left.
- Right Rotation: Rebalances the tree by rotating nodes to the right.
- Left-Right Rotation: A combination of left and right rotations.
- Right-Left Rotation: A combination of right and left rotations.
These rotations ensure that the AVL tree remains balanced after insertions and deletions.
AVL Insert Node Implementation
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
int height; // Height of the node
};
// Function to get the height of a node
int height(struct TreeNode* node) {
if (node == NULL)
return 0;
return node->height;
}
// Function to get the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1; // New node is initially added at leaf
return newNode;
}
// Function to right rotate subtree rooted with y
struct TreeNode* rightRotate(struct TreeNode* y) {
struct TreeNode* x = y->left;
struct TreeNode* 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;
}
// Function to left rotate subtree rooted with x
struct TreeNode* leftRotate(struct TreeNode* x) {
struct TreeNode* y = x->right;
struct TreeNode* 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;
}
// Get the balance factor of a node
int getBalance(struct TreeNode* node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// Function to insert a node into the AVL tree
struct TreeNode* insert(struct TreeNode* node, int data) {
// Perform normal BST insertion
if (node == NULL)
return (createNode(data));
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else // Equal keys not allowed in BST
return node;
// Update height of this ancestor node
node->height = 1 + max(height(node->left), height(node->right));
// Get the balance factor to check if this node became unbalanced
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && data < node->left->data)
return rightRotate(node);
// Right Right Case
if (balance < -1 && data > node->right->data)
return leftRotate(node);
// Left Right Case
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// Function to print the inorder traversal of the AVL tree
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Main function
int main() {
struct TreeNode* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Inorder traversal of the AVL tree: ");
inOrderTraversal(root);
printf("\n");
return 0;
}
Output:
Inorder traversal of the AVL tree: 10 20 30 35 40 50
AVL Delete Node Implementation
Below is an implementation of the AVL tree deletion operation in C. Deletion in AVL trees involves standard binary search tree deletion followed by AVL tree balancing to maintain the AVL property.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
int height;
} TreeNode;
int max(int a, int b) {
return (a > b) ? a : b;
}
int getHeight(TreeNode *N) {
if (N == NULL)
return 0;
return N->height;
}
TreeNode* newNode(int data) {
TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
TreeNode *rightRotate(TreeNode *y) {
TreeNode *x = y->left;
TreeNode *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
TreeNode *leftRotate(TreeNode *x) {
TreeNode *y = x->right;
TreeNode *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
int getBalance(TreeNode *N) {
if (N == NULL)
return 0;
return getHeight(N->left) - getHeight(N->right);
}
TreeNode* insert(TreeNode* node, int data) {
if (node == NULL)
return(newNode(data));
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else // Equal data not allowed in BST
return node;
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && data < node->left->data)
return rightRotate(node);
// Right Right Case
if (balance < -1 && data > node->right->data)
return leftRotate(node);
// Left Right Case
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
TreeNode * minValueNode(TreeNode* node) {
TreeNode* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
void inOrderTraversal(TreeNode *root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%c ", root->data);
inOrderTraversal(root->right);
}
}
TreeNode* deleteNode(TreeNode* root, int data) {
if (root == NULL)
return root;
// Standard BST delete
if (data < root->data)
root->left = deleteNode(root->left, data);
else if (data > root->data)
root->right = deleteNode(root->right, data);
else {
if ((root->left == NULL) || (root->right == NULL)) {
TreeNode *temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
TreeNode* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(getHeight(root->left), getHeight(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;
}
int main() {
TreeNode *root = NULL;
char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
int n = sizeof(letters) / sizeof(letters[0]);
for (int i = 0; i < n; i++) {
root = insert(root, letters[i]);
}
inOrderTraversal(root);
printf("\nDeleting 'C'\n");
root = deleteNode(root, 'C');
inOrderTraversal(root);
return 0;
}
Output:
A B C D E F G H
Deleting 'C'
A B D E F G H
Time Complexity:
In AVL trees, search, insertion, and deletion operations have a time complexity of O(log n), where n is the number of nodes in the tree. This is because AVL trees maintain balance, ensuring that the height of the tree remains logarithmic with respect to the number of nodes.
Advantages of AVL Trees:
- Guaranteed Balanced Structure: AVL trees guarantee a balanced structure, leading to predictable and efficient search, insertion, and deletion operations.
- Optimal Time Complexity: With logarithmic time complexity for basic operations, AVL trees are suitable for applications where performance is critical.
Disadvantages of AVL Trees:
- More Overhead: Maintaining balance in AVL trees requires additional bookkeeping compared to regular binary search trees. This overhead can result in slightly slower insertion and deletion operations.
- Complex Implementation: Implementing AVL trees can be more complex compared to simpler binary search trees due to the need for balancing operations.
Despite these drawbacks, AVL trees are widely used in practice and serve as a foundational data structure in various applications where efficient search, insertion, and deletion operations are required.
