AVL Tree Assignment
Uploaded by
shaidurrahaman2004AVL Tree Assignment
Uploaded by
shaidurrahaman2004East West University
Data Structure Assignment
Instructor: Md. Manowarul Islam
Student Name : Kazi Shaidur Rahaman
Id : 2023-3-60-015
Department : CSE
Introduction
AVL Tree is the first Self- Each node stores a
Balancing Binary Search
Tree- Introduced in 1962
Balance Factor (BF). Allowed BF
by Adelson-Velsky and BF = height(left subtree) – values: –1, 0, +1
Landis. height(right subtree)
2
Properties
Balance Factor (BF): –1, 0, +1
Height Difference Rule-1:
If |BF| > 1 → the tree becomes unbalanced
Height Difference Rule-2:
To restore balance → Rotations are used
3
Rotation
4
Insertion Steps
• Insert the new node
following BST rules
• Update the height of
nodes
• Compute the Balance
Factor (BF)
• If BF not in {–1, 0, +1}
→ perform appropriate
Rotation
• Tree becomes balanced
again
5
AVL Tree Code
// Structure for an AVL tree node // Function to calculate the balance factor of a
typedef struct Node { node
int data; int getBalance(Node* N) {
struct Node* left; if (N == NULL)
struct Node* right; return 0;
int height; return height(N->left) - height(N->right);
} Node; }
// Function to get the height of a node
// Right rotate subtree rooted with y
int height(Node* N) {
Node* rightRotate(Node* y) {
if (N == NULL)
return 0; Node* x = y->left;
return N->height; Node* T2 = x->right;
}
6
// Perform rotation // Left rotate subtree rooted with x
x->right = y; Node* leftRotate(Node* x) {
y->left = T2; Node* y = x->right;
Node* T2 = y->left;
// Perform rotation
// Update heights
y->left = x;
y->height = 1 + max(height(y->left), x->right = T2;
height(y->right));
// Update heights
x->height = 1 + max(height(x->left),
height(x->right)); x->height = 1 + max(height(x->left), height(x-
>right));
y->height = 1 + max(height(y->left), height(y-
// Return new root >right));
// Return new root
return x;
return y;
}
}
7
// Function to insert a node into the AVL tree if (data < node->data)
Node* insert(Node* node, int data) { node->left = insert(node->left, data);
// 1. Perform the normal BST insertion else if (data > node->data)
if (node == NULL) {
node->right = insert(node->right,
Node* newNode = data);
(Node*)malloc(sizeof(Node));
else // Equal keys are not allowed in BST
newNode->data = data;
newNode->left = NULL; return node;
newNode->right = NULL;
newNode->height = 1; // New node is // 2. Update height of the current node
initially added at leaf
node->height = 1 + max(height(node-
return newNode; >left), height(node->right));
}
8
// 3. Get the balance factor of this node (to // Left Right Case
check whether this node became unbalanced)
if (balance > 1 && data > node->left->data) {
int balance = getBalance(node);
node->left = leftRotate(node->left);
// If this node becomes unbalanced, then
there are 4 cases return rightRotate(node);
}
// Left Left Case // Right Left Case
if (balance > 1 && data < node->left->data) if (balance < -1 && data < node->right->data) {
return rightRotate(node); node->right = rightRotate(node->right);
return leftRotate(node);
// Right Right Case }
if (balance < -1 && data > node->right- // return the (unchanged) node pointer
>data)
return node;
return leftRotate(node);
}
9
Time Complexity
10
Conclusion
❑ AVL TREE = SELF-BALANCING BINARY SEARCH
TREE
❑ GUARANTEES O(LOG N) FOR SEARCH, INSERTION,
DELETION
❑ USES ROTATIONS TO MAINTAIN BALANCE
❑ BEST CHOICE WHEN FAST SEARCHING IS
REQUIRED
11
