The AVL Tree is a binary search tree that has an additional
balance condition. This balance condition must be easy to maintain
and ensures that the depth of the tree is O(logN). The simplest idea
is to require that the left and right sub-trees have the same
height. Recursion dictates that this idea applies to all nodes in
the tree, since each node is itself a root of some sub-tree.
AVL is a height balanced tree. A height balanced tree is one in
which the difference in the height of the two sub-trees for any
node is less than or equal to some specified amount.
Balance Factor
Balance is defined by height of left sub-tree -
height of right sub-tree. For an AVL tree the value of the
balance factor of any node is -1, 0, or 1. If it is other than these
three values then the tree is not balanced.
Insertion In AVL Tree
We can insert a new node in an AVL tree by finding its
appropriate position similar to that of the binary search tree.
- If the data item with key 'k' is inserted into an empty AVL
tree, then the node with key 'k' is set to be the root node.
- If tree contains only single node i.e. root node then the
insertion of the node with key 'k' depends upon its value. If the
value of 'k' is less than the key value of the root then it is
inserted to the left of the root otherwise right of the root.
- If on inserting the node with key 'k' the height of the right
sub-tree of the root has increased. Similarly if on inserting a node
with key 'k' the height of the left sub-tree of the root is
increased.
LL Rotation: The new node 'x' is inserted in the left
sub-tree of root node whose(root) balance factor becomes +2 after
insertion. Below in the Fig 2 we will see the LL rotation.
RR Rotation: Unbalance occurs due to insertion in the right
sub-tree of the right child of the root node and balance factor of
root node becomes -2.We will see the RR rotation in the following
Fig 3.
LR Rotation: Unbalance occurred due to the insertion in the
right sub-tree of the left child of the root node. We will clear
this rotation in the following Fig 4.
RL Rotation: Unbalance occurred due to the insertion in the
left subtree of the right child of the root node. We will clear this
rotation in the following Fig 5.
Insertion In AVL Tree Using C
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct 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;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct 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;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* 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;
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct Node *root = NULL;
int ch,value;
while(1)
{
printf("\n1.insert");
printf("\n2.preorder");
printf("\n3.exit");
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nenter the value:");
scanf("%d",&value);
root=insert(root,value);
break;
case 2:preOrder(root);
break;
case 3:return 0;
}
}
return 0;
}
Deletion In AVL Tree
The deletion of a node from an AVL tree is exactly the same as
the deletion of a node from the BST. The sequence of steps to be
followed in deleting a node from an AVL tree is as follows:
- Initially, the AVL tree is searched to find the node to be
deleted.
- The procedure used to delete a node in an AVL tree is the same
as deleting the node in the binary search tree.
- After deletion of the node, check the balance factor of each
node.
- Rebalance the AVL tree if the tree is unbalanced. In this
situation we need some rotations.
R0 And L0 Rotation: When we delete a node and that node is
present at the right sub-tree. In this situation th parent node of
left sub-tree whose balance factor is 0 is rotated in right
direction. Similarly for L0 rotation, the deleted node is present at
left sub-tree of root node. We will see the rotation in following Fig
1.
R1 And L1 Rotation: It is same as R0 or L0 rotation. Only the
difference is that balance factor of parent node of left sub-tree
or right sub-tree is +1 here.We will see the rotation in following
Fig 2.
R(-1) And L(-1) Rotation: In this case balance factor of parent node is -1. we will see the rotation in following Fig 3.
Deletion In AVL Tree Using C
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct 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;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct 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;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
/* 1. Perform the normal BST rotation */
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
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;
}
struct Node * minValueNode(struct Node* node)
{
struct Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
struct Node* deleteNode(struct Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller than the
// root's key, then it lies in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater than the
// root's key, then it lies in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is
// the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
struct Node *temp = root->left ? root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
struct Node* temp = minValueNode(root->right);
// Copy the inorder successor's data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
// check whether this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// 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;
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct Node *root = NULL;
int ch,value;
while(1)
{
printf("\n1.insert");
printf("\n2.preorder");
printf("\n3.delete");
printf("\n4.exit");
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nenter the value:");
scanf("%d",&value);
root=insert(root,value);
break;
case 2:preOrder(root);
break;
case 3:printf("\n enter value for deletion:");
scanf("%d",&value);
root=deleteNode(root,value);
break;
case 4:return 0;
}
}
return 0;
}
Happy Exploring!
Posts
No comments:
Post a Comment