C Programming Data Structures Avl Trees And Rotations Complete Guide
Understanding the Core Concepts of C Programming data structures AVL Trees and Rotations
C Programming: Detailed Overview of Data Structures - AVL Trees and Rotations
AVL Trees are height-balanced binary search trees (BSTs) where the difference between the heights of the left and right subtrees cannot be more than one for all nodes. This property ensures that operations like search, insert, and delete can perform in O(log n) time complexity. AVL trees are named after their inventors, Georgy Adelson-Velsky and Evgenii Landis, who described them in their 1962 paper.
Structure of an AVL Tree
An AVL Tree is a binary tree with an additional property of balance factor defined for every node. The balance factor is calculated as the difference between the heights of the left and right subtrees:
[ \text{Balance Factor} = \text{Height of Left Subtree} - \text{Height of Right Subtree} ]
The balance factor for any node should be -1, 0, or 1. If the balance factor becomes less than -1 or greater than 1 after an insertion or deletion, the tree must be rebalanced.
Why Use AVL Trees?
Unlike unbalanced binary search trees, AVL trees ensure efficient access and modification. They maintain their logarithmic height, making them suitable for use as a dynamic set or dictionary where insertion, deletion, and lookup operations need to be performed as quickly as possible.
Rotations in AVL Trees
Rotations are the main mechanism by which AVL trees are rebalanced after insertion or deletion. Here are the different types of rotations:
Right Rotation (Single Rotation):
- Occurs when the insertion happens in the left subtree of the left child.
- This rotation fixes the right-heavy imbalance on the left subtree of the root.
Left Rotation (Single Rotation):
- Occurs when the insertion happens in the right subtree of the right child.
- This rotation fixes the left-heavy imbalance on the right subtree of the root.
Left-Right Rotation (Double Rotation):
- Involves a left rotation on the left child followed by a right rotation on the root.
- Fixes right-heavy imbalance on the left subtree of the root.
Right-Left Rotation (Double Rotation):
- Involves a right rotation on the right child followed by a left rotation on the root.
- Fixes left-heavy imbalance on the right subtree of the root.
Implementation of AVL Trees in C:
Below is a simplified example of how AVL trees can be implemented in C, focusing on insertion and rotation operations.
#include <stdio.h>
#include <stdlib.h>
// Node structure
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
} Node;
// Function to allocate 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; // new node is initially added at leaf
return (node);
}
// Function to get height
int height(Node *N) {
if (N == NULL)
return 0;
return N->height;
}
// Function to get balance factor
int getBalance(Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// 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;
}
// 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;
}
// Function to insert a new key to the BST
Node* insert(Node* node, int key) {
// Perform the 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;
// Update height of this ancestor node
node->height = 1 + max(height(node->left), height(node->right));
// Get the balance factor of this ancestor node to check whether this node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced, then 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;
}
Conclusion
Online Code run
Step-by-Step Guide: How to Implement C Programming data structures AVL Trees and Rotations
Introduction to AVL Trees
An AVL Tree is a self-balancing Binary Search Tree (BST) 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 operations like search, insertion, and deletion.
Basic Structure of an AVL Tree Node
The basic structure of an AVL Tree node includes:
- A key/data value.
- Pointers to the left and right child nodes.
- A height attribute which denotes the height of the node in the tree.
Here's how you define an AVL Tree node in C:
#include <stdio.h>
#include <stdlib.h>
// An AVL tree node
struct AVLNode {
int key;
struct AVLNode *left;
struct AVLNode *right;
int height;
};
// A utility function to get the height of the tree
int height(struct AVLNode *N) {
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
Creating a New AVL Node
To insert new elements into the AVL Tree, we will need a function to create a new AVL node with the given key and initialize its children as NULL and its height as 1.
// Helper function that allocates a new node with the given key and
// NULL left and right pointers
struct AVLNode* newNode(int key) {
struct AVLNode* node = (struct AVLNode*) malloc(sizeof(struct AVLNode));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
Rotations
AVL Trees require special functions to perform rotations when the tree becomes unbalanced. There are four types of rotations: Right Rotation, Left Rotation, Right-Left Rotation, and Left-Right Rotation.
Right Rotation
This rotation is performed on the unbalanced sub-tree's root node if the node's balance factor is greater than 1 and the node's left child's balance factor is also greater than or equal to 0.
Here's the implementation of Right Rotation:
// Right rotate subtree rooted with y
struct AVLNode *rightRotate(struct AVLNode *y) {
struct AVLNode *x = y->left;
struct AVLNode *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;
}
Left Rotation
This rotation is performed on the unbalanced sub-tree's root node if the node's balance factor is less than -1 and the node's right child's balance factor is also less than or equal to 0.
Here's the implementation of Left Rotation:
// Left rotate subtree rooted with x
struct AVLNode *leftRotate(struct AVLNode *x) {
struct AVLNode *y = x->right;
struct AVLNode *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;
}
Left-Right Rotation
This rotation is performed if the node's balance factor is greater than 1 and the node's left child's balance factor is less than 0.
Here's the implementation of Left-Right Rotation:
// Left Right Rotate
struct AVLNode* leftRightRotate(struct AVLNode *Z) {
Z->left = leftRotate(Z->left);
return rightRotate(Z);
}
Right-Left Rotation
This rotation is performed if the node's balance factor is less than -1 and the node's right child's balance factor is greater than 0.
Here's the implementation of Right-Left Rotation:
// Right Left Rotate
struct AVLNode* rightLeftRotate(struct AVLNode *Z) {
Z->right = rightRotate(Z->right);
return leftRotate(Z);
}
Inserting a Node
Now, let's implement the function to insert a node into the AVL Tree while ensuring it remains balanced:
// Get Balance factor of node N
int getBalance(struct AVLNode *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key in the subtree rooted
// with node and returns the new root of the subtree.
struct AVLNode* insert(struct AVLNode* node, int key) {
// 1. Perform the 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, then 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;
}
Traversal of AVL Tree
We can use Preorder, Inorder, or Postorder traversal to print the keys of the AVL Tree. Here, we'll use Preorder Traversal.
// Function to print preorder traversal of the tree.
void preOrder(struct AVLNode *root) {
if(root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
Full Example Code
Let's combine all these steps into a complete example code for inserting nodes into an AVL Tree and performing a preorder traversal.
#include <stdio.h>
#include <stdlib.h>
// An AVL tree node
struct AVLNode {
int key;
struct AVLNode *left;
struct AVLNode *right;
int height;
};
// A utility function to get the height of the tree
int height(struct AVLNode *N) {
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
// Helper function that allocates a new node with the given key and
// NULL left and right pointers
struct AVLNode* newNode(int key) {
struct AVLNode* node = (struct AVLNode*) malloc(sizeof(struct AVLNode));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
// Right rotate subtree rooted with y
struct AVLNode *rightRotate(struct AVLNode *y) {
struct AVLNode *x = y->left;
struct AVLNode *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;
}
// Left rotate subtree rooted with x
struct AVLNode *leftRotate(struct AVLNode *x) {
struct AVLNode *y = x->right;
struct AVLNode *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 Balance factor of node N
int getBalance(struct AVLNode *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key in the subtree rooted with node
// and returns the new root of the subtree.
struct AVLNode* insert(struct AVLNode* node, int key) {
// 1. Perform the 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, then 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 print preorder traversal of the tree.
void preOrder(struct AVLNode *root) {
if(root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
// Driver program to test above functions
int main() {
struct AVLNode *root = NULL;
/* Constructing tree given in the above figure */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
printf("Preorder traversal of the constructed AVL tree is \n");
preOrder(root);
return 0;
}
Explanation of the Code
Initialization & Rotation Functions: These functions create the initial AVL node, perform right and left single rotations, as well as left-right, and right-left double rotations.
Insertion Function: The
insertfunction inserts a new node into the AVL Tree and balances the tree using the rotations we defined earlier.Traversal Function: The
preOrderfunction helps us traverse the AVL Tree in Preorder, printing out each key along the way.Main Function: The
mainfunction demonstrates the creation of an AVL Tree by inserting keys one by one and then prints out the resulting AVL Tree using the Preorder traversal.
Running the Code
To run this C code follow these steps:
- Copy the provided C code into a file named
avl_tree.c. - Open your terminal or command prompt.
- Navigate to the directory containing
avl_tree.c. - Compile the code using the following command:
gcc avl_tree.c -o avl_tree
- Run the compiled program:
./avl_tree
You should see the following output indicating the AVL Tree’s structure after insertions:
Top 10 Interview Questions & Answers on C Programming data structures AVL Trees and Rotations
1. What is an AVL Tree?
Answer: An AVL Tree is a self-balancing binary search tree named after its creators, Adelson-Velskii and Landis. In an AVL Tree, the heights of the left and right subtrees of any node differ by no more than one. If they differ by more than one, the tree performs rotations to restore balance.
2. What are the advantages of using an AVL Tree?
Answer: The main advantages of AVL Trees are their ability to maintain balance automatically, ensuring that the height remains (O(\log n)). This guarantees that basic operations like insertion, deletion, and lookup remain efficient at (O(\log n)).
3. How does the balance factor contribute to maintaining balance in AVL Trees?
Answer: The balance factor of a node is the difference in heights between the left and right subtrees. AVL Trees require all nodes to have a balance factor of -1, 0, or 1. Any deviation triggers rotations to maintain this balance.
4. What are the types of rotations used in AVL Trees?
Answer: There are four types of rotations used in AVL Trees:
- Right Rotation (Single Rotation): Used when a left-heavy node is found.
- Left Rotation (Single Rotation): Used when a right-heavy node is found.
- Left-Right Rotation (Double Rotation): Used when the left subtree is right-heavy.
- Right-Left Rotation (Double Rotation): Used when the right subtree is left-heavy.
5. Define and explain a Right Rotation in AVL Trees.
Answer: A right rotation is performed when a node becomes left-heavy and its left child is also left-heavy. It involves moving the left child up to the parent's position and adjusting the other pointers accordingly. This rotation ensures the AVL Tree remains balanced.
6. Define and explain a Left Rotation in AVL Trees.
Answer: A left rotation is performed when a node becomes right-heavy and its right child is also right-heavy. The right child takes the place of its parent, and the original parent becomes the left child of the new parent. This helps in balancing the tree.
7. When and why do you perform a Left-Right Rotation?
Answer: A left-right rotation is used when a node is left-heavy and its left child is right-heavy. This rotation involves a left rotation on the left child, followed by a right rotation on the unbalanced node to restore balance.
8. Can you explain the purpose of Double Rotation (Left-Right/Right-Left) in AVL Trees?
Answer: Double rotations are used to ensure balance when a node is unbalanced in a more complex manner. They first correct the imbalance within the heavy subtree (either through left or right rotation) and then balance the larger subtree with a final rotation. This results in a more evenly balanced tree.
9. How do you update the balance factor after performing any type of rotation?
Answer: After each rotation, the balance factors of the nodes involved are updated. This involves recalculating the heights of the subtrees and adjusting the balance factors based on the new heights. The balance factors are crucial for determining when further rotations are needed.
10. What is the algorithmic complexity for insertion and deletion operations in AVL Trees?
Answer: Both insertion and deletion operations in AVL Trees have a time complexity of (O(\log n)) because the tree's height is always kept logarithmic. Rotations, although additional operations, are performed locally and do not significantly affect the overall complexity.
Login to post a comment.