C Programming: Data Structures - AVL Trees and Rotations
Introduction to AVL Trees: AVL trees are self-balancing binary search trees named after their inventors, G. M. Adelson-Velsky and E. M. Landis. Introduced in 1962, AVL trees maintain their balance by ensuring that the height difference of the left and right subtrees (known as the balance factor) of any node is at most one. This balance ensures that operations like insertion, deletion, and lookup can be performed in (O(\log n)) time, where (n) is the number of nodes in the tree.
Properties of AVL Trees:
- Binary Search Tree (BST) Property: Every node in the AVL tree is a valid BST, meaning the left subtree of any node contains values less than the node, and the right subtree contains values greater than the node.
- Balance Factor: For an AVL tree, the balance factor of each node must be -1, 0, or +1. The balance factor is defined as the height of the left subtree minus the height of the right subtree.
- Height Balancing: The difference in heights between the left and right subtrees of any node must not exceed 1. If it does, the tree is rotated to restore balance.
Types of Violations and Rotations: When a node is inserted or deleted, the AVL tree may become unbalanced. There are four possible violations based on the insertion/deletion point:
- Left-Left (LL) Case: This occurs when a left child is inserted into the left subtree of an already left-heavy node.
- Right-Right (RR) Case: This occurs when a right child is inserted into the right subtree of an already right-heavy node.
- Left-Right (LR) Case: This occurs when a right child is inserted into the left subtree of an already left-heavy node.
- Right-Left (RL) Case: This occurs when a left child is inserted into the right subtree of an already right-heavy node.
Rotations in AVL Trees: To restore balance, rotations are performed. There are two fundamental types of rotations:
- Single Rotation (Right and Left):
- Right Rotation (LL Case): A right rotation is performed around the node (y). This rotation fixes the LL imbalance.
- Left Rotation (RR Case): A left rotation is performed around the node (x). This rotation fixes the RR imbalance.
- Double Rotation (LR and RL):
- Left-Right Rotation (LR Case): This rotation is a combination of a left rotation on the left child of the unbalanced node followed by a right rotation on the unbalanced node.
- Right-Left Rotation (RL Case): This rotation is a combination of a right rotation on the right child of the unbalanced node followed by a left rotation on the unbalanced node.
Implementation in C: Below is a basic implementation of AVL Trees including insertion and necessary rotations in C:
#include <stdio.h>
#include <stdlib.h>
// Node Structure
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
} Node;
// Function to get the height of a node
int height(Node *N) {
if (N == NULL)
return 0;
return N->height;
}
// Function to get the maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
// Function to allocate a new node with the given key and NULL left and right pointers
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return node;
}
// Function to right rotate subtree rooted with y
Node *rightRotate(Node *y) {
Node *x = y->left;
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;
}
// Function to left rotate subtree rooted with x
Node *leftRotate(Node *x) {
Node *y = x->right;
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;
}
// Get the balance factor of node N
int getBalance(Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Insert a node in the AVL tree and perform necessary rotations to balance the tree
Node* insert(Node* node, int key) {
// 1. Perform normal 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;
// 2. Update height of this ancestor node
node->height = 1 + max(height(node->left), height(node->right));
// 3. Get the balance factor of this ancestor node to check whether this node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced, 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;
}
// Function to traverse the tree in-order
void inOrder(Node *root) {
if(root != NULL) {
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
}
// Main function to test the AVL tree operations
int main() {
Node *root = NULL;
// Inserting keys one by one
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 constructed AVL tree is \n");
inOrder(root);
return 0;
}
Explanation of the Code:
- Node Structure Definition: Defines a struct for AVL nodes including a key, pointers to left and right children, and an integer for the height.
- Functions for Height, Maximum Value, and New Nodes: Functions to return the height of a node, get the maximum of two integers, and create a new node.
- Right and Left Rotations: Implementations for left and right rotations to maintain AVL properties.
- Insert Function: Handles insertion by following the BST property and ensuring that the AVL balance condition is met through rotations.
- In-Order Traversal: In-order traversal function to print the contents of the AVL tree in sorted order.
Conclusion: AVL Trees are crucial in scenarios where frequent insertions and deletions are expected, ensuring the tree remains balanced and operations remain efficient. Understanding the balancing mechanism, rotations, and their implementation in C provides a strong foundation in advanced data structures. AVL Trees are a step beyond binary search trees, offering performance guarantees that make them preferred in performance-critical applications.
Certainly! Let's create a comprehensive guide for beginners on AVL Trees and Rotations using C programming, including examples of frontend, backend, data flow, and running the application step-by-step.
Understanding AVL Trees and Rotations
AVL Trees are self-balancing binary search trees where the difference between heights of left and right subtrees cannot be more than one for all nodes. If at any time they become unbalanced, rotations (left or right or left-right or right-left) are performed to restore the balance.
Step 1: Setting Up the C Program
Backend (C Code)
Here's a simple C program implementing AVL Trees and includes operations for insertion and balancing using rotations.
#include <stdio.h>
#include <stdlib.h>
// Define the Node structure
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
} Node;
// Function to calculate the height of a node
int height(Node *node) {
if (node == NULL)
return 0;
return node->height;
}
// Function to create a new node
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
// Function to perform a right rotation
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;
}
// Function to perform a left rotation
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;
}
// Function to get the balance factor of a node
int getBalance(Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Function to insert a node into the tree
Node* insert(Node* node, int key) {
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 // Duplicate 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;
}
// Function to print pre-order traversal of the AVL tree
void preOrder(Node *root) {
if(root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
// Helper function to find the maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
// Main function to run the code
int main() {
Node *root = NULL;
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
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("Preorder traversal of the constructed AVL tree is \n");
preOrder(root);
return 0;
}
Step 2: Frontend Setup
For a beginner, setting up frontend can be complex, but here’s a simple text-based interface using a C program itself to interact with our AVL tree.
But typically, the frontend could be a web application that interacts with the backend through API calls. However, to keep things simple, let's consider a console-based frontend for demonstration purposes.
Step 3: Data Flow
- User Input: The user inputs a series of integers that need to be inserted into the AVL Tree.
- Backend Processing:
- Insert the number into the AVL Tree.
- If the AVL Tree goes out of balance, perform the necessary rotations (left, right, left-right, or right-left).
- Re-balance the AVL Tree.
- Output: The AVL Tree in pre-order traversal is printed to the console.
Step 4: Running the Application
Backend Compilation and Execution
To compile and run the C application:
- Save the code as
avl_tree.c. - Open a terminal and navigate to the directory where the file is saved.
- Compile the code using the GCC compiler:
gcc avl_tree.c -o avl_tree - Run the compiled program:
./avl_tree
The output will be the pre-order traversal of the AVL tree after inserting all elements.
Conclusion
Through this example, you've learned to set up an AVL Tree in C, managed rotations to keep the tree balanced, and demonstrated the process within a simple C console application. For production-level applications, this backend could be integrated with a frontend and exposed via API calls. Real-world applications often involve complex frontend and backend interactions, but the principles remain the same.
Certainly! Here is a comprehensive set of "Top 10 Questions and Answers" on C Programming Data Structures with a focus on AVL Trees and Rotations:
Top 10 Questions and Answers on AVL Trees and Rotations in C Programming
1. What is an AVL Tree?
Answer: An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. This ensures that the tree remains approximately balanced, leading to O(log n) time complexity for search, insert, and delete operations.
2. How does an AVL Tree maintain balance?
Answer: AVL Trees maintain balance through rotations. Whenever a node is inserted or deleted, the tree is traversed back to the root, and at each node, the balance factor (the difference between the height of the left and right subtrees) is recalculated. If the balance factor becomes more than 1 or less than -1, rotations are performed to maintain balance.
3. What types of rotations are used in AVL Trees?
Answer: There are four types of rotations used in AVL Trees to rebalance the tree:
- Right Rotation (Single Rotation): This is applied when there is a left-heavy imbalance. It involves rotating the unbalanced node to the right.
- Left Rotation (Single Rotation): This is applied when there is a right-heavy imbalance. It involves rotating the unbalanced node to the left.
- Left-Right Rotation (Double Rotation): This is applied when there is a left-heavy imbalance with a right-heavy subtree. It involves performing a left rotation on the left child of the unbalanced node, followed by a right rotation on the unbalanced node.
- Right-Left Rotation (Double Rotation): This is applied when there is a right-heavy imbalance with a left-heavy subtree. It involves performing a right rotation on the right child of the unbalanced node, followed by a left rotation on the unbalanced node.
4. Can you explain a right rotation with an example?
Answer: A right rotation is typically performed when the left subtree is taller by more than one level, indicating a left-heavy imbalance.
Example: Suppose we have the following tree:
z
/
y
\
T2
Here, the tree is left-heavy at node z. To perform a right rotation about z, we make y the new root and z the right child of y. T2 then becomes the left child of z.
After the right rotation, the tree becomes:
y
\
z
/
T2
5. How do you calculate the height of a node in an AVL Tree?
Answer: The height of a node in an AVL Tree can be calculated using a recursive function. If the node is NULL, its height is considered to be -1 (to handle the leaf node scenario correctly). Otherwise, the height is the maximum height of its left and right subtrees plus one.
C Code Example:
int height(struct Node* node) {
if (node == NULL)
return -1;
return node->height;
}
6. How do you perform an insertion in an AVL Tree?
Answer: Insertion in an AVL Tree involves the following steps:
- Perform the standard binary search tree (BST) insertion.
- Update the height of the ancestor nodes.
- Get the balance factor of the ancestor nodes.
- Perform rotations if the balance factor is not within the acceptable range (-1, 0, 1).
C Code Example:
struct Node* insert(struct Node* node, int key) {
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 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;
}
7. What is the balance factor of a node in an AVL Tree?
Answer: The balance factor of a node is the difference between the heights of its right and left subtrees. It is calculated as:
balanceFactor = height(rightSubtree) - height(leftSubtree)
A node with a balance factor of -1, 0, or 1 is considered balanced. A balance factor outside this range indicates that the tree needs rebalancing.
8. How do you delete a node from an AVL Tree?
Answer: Deleting a node from an AVL Tree involves the following steps:
- Perform the standard BST deletion.
- Update the height of the ancestor nodes.
- Get the balance factor of each ancestor node.
- Perform rotations if the balance factor is not within the acceptable range.
C Code Example:
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else { // Node with only one child or no child
struct Node* temp = NULL;
if (root->left == NULL) {
temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
temp = root->left;
free(root);
return temp;
}
temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
if (root == NULL)
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;
}
9. Why do AVL Trees use height balancing instead of weight balancing?
Answer: AVL Trees use height balancing because it ensures that the height of the tree is kept logarithmic relative to the number of nodes, which guarantees O(log n) time for search, insert, and delete operations. Weight balancing could lead to less efficient operations because it does not guarantee height balance, and the tree could become unbalanced even with small changes, leading to inefficient operations.
10. What are the advantages and disadvantages of AVL Trees compared to other self-balancing binary search trees?
Answer: Advantages:
- Provides O(log n) time complexity for search, insert, and delete operations.
- Ensures the tree remains approximately balanced after each insertion and deletion.
Disadvantages:
- More complex to implement compared to non-self-balancing binary search trees.
- Each insertion and deletion may require rotations, adding overhead.
- Requires additional memory to store height information at each node.
Understanding AVL Trees and their rotations is crucial for managing balanced data structures in C Programming, ensuring efficient operations and data retrieval.