Unit-4 3

AVL Trees
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two
subtrees of any node differ by at most one; therefore, it is also said to be height-balanced.
Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases,
where n is the number of nodes in the tree prior to the operation. The AVL tree is named after
its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper
"An algorithm for the organization of information."
Definition: An empty binary search tree is an AVL tree. If T is a non empty binary search tree
with TL and TR as its left and right subtrees, then T is an AVL tree iff
(1) TL and TR are AVL Trees and
(2) | hL – hR | <=1 where hL and hR are the heights of TL and TR respectively.
In other words, an AVL tree is a binary search tree in which the balance factor for each
and every node of the tree should be 0,1 or -1.
The balance factor of a node is the height of its right subtree minus the height of its left
subtree, and a node with balance factor 1, 0, or -1 is considered balanced.
The balance factor bf(x) of a node is defined as,
bf(x) = height of left sub-tree of x – height of right subtree of x
A node with any other balance factor is considered unbalanced and requires rebalancing the
tree. The balance factor is either stored directly at each node or computed from the heights of
the subtrees.
Height of an AVL Tree:

We will obtain a bound on the height of an AVL tree that n nodes in it. Let Nh be the minimum
number of nodes in an AVL tree if height h. In the worst case the height of one of subtrees is
h-1, and the height of the other is h-2, both these subtrees are also AVL trees. Hence,
Nh= Nh-1 + Nh-2 + 1 , where N1=1 and N2=2
Notice the similarity between thes definition for Nh and the definition of the Fibonacci numbers
Fn= Fn-1 + Fn-2
If there are n nodes in the tree, then its height h is at most O(log n).
The various operations that can be performed on AVL tree are:
 Inserttion : the process of inserting a node into the binary search tree.
 Deletion : The process of deleting a node from Binary Search Tree.
 Search: The process of verifying whether a particular node exist in the BST or not.
 Traversal: The process of visiting each and every node once.
Insertion:
The process of inseting a node into an AVL tree is same as inserting a node into a Binary
Search Tree. i.e. Compare the node to be inserted with the root. If the node value is less than
the root insert into the left subtree , if the node value is greater than the root then insert into
the right subtree. In this procees a new node will be always inserted as the leaf node. Then,
 Insert operation may cause balance factor to become 2 or –2 for some node
 only nodes on the path from insertion point to root node have possibly changed in
height
 So after the Insert, go back up to the root , node by node, updating heights
 If a new balance factor (the difference hleft-hright) of a node in this path is 2 or –2,
adjust tree by doing rotation around the node.
 Let the node that needs rebalancing be .
 The rebalancing is performed through any of four rotation algorithms.
 Thus once we perform a rotation at node , then we do not require to perform any
rotation at any ancestor of .
Different Rotations in AVL tree:
Some modifications done on AVL tree in order to rebalance it are called rotations of AVL
tree.
Rotations are mainly classified into two types. They are :
(If the node to be rebalanced is 
o Outside Cases (require single rotation) :
 Insertion into left subtree of left child of .( LL Rotation)
 Insertion into right subtree of right child of . (RR Rotation)
o Inside Cases (require double rotation) :
 Insertion into right subtree of left child of .(RL Rotation)
 Insertion into left subtree of right child of . (LR Rotation)
a) LL Rotation: (Left Left Case )
When BST becomes unbalanced, due to a node is inserted into the left subtree of the left
subtree of C, then we perform LL rotation, LL rotation is clockwise rotation, which is applied
on the edge below a node having balance factor 2.
b) RR Rotation: ( Right Right Case )
When BST becomes unbalanced, due to a node is inserted into the right subtree of the
right subtree of A, then we perform RR rotation, RR rotation is an anticlockwise rotation,
which is applied on the edge below a node having balance factor -2
Right Rotation
b) RL Rotation ( Right Left case): A node is inserted in the Right Subtree of the
left child of unbalanced node
z z x
/ \ / \ / \
y T4 Right Rotate (y) x T4 Left Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
d) LR Rotation (Left Right Case) : A node is inserted in the Left Subtree of the
Right child of unbalanced node
z z x
/ \ / \ / \
T1 y Left Rotate (y) T1 x Right Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Deletion:
The procedure for deleting a node in AVL tree is:
 Delete the node using BST deletion procedure.

( i.e. If the node is a leaf, remove it. If the node is not a leaf, replace it with either the
largest in its left subtree (inorder predecessor) or the smallest in its right subtree
(inorder successor), and remove that node. )
 After deletion, retrace the path back up the tree (parent of the replacement) to the root,
adjusting the balance factors as needed.
 If the balance factor becomes -2 or 2 then the subtree is unbalanced and needs to be
rotated to fix it.
 If balance factor is greater than 1, then the current node is unbalanced and we are
either in Left Left case or Right Left case. To check whether it is Left Left case or Right
Left case, get the balance factor of left subtree. If balance factor of the left subtree is
greater than or equal to 0, then it is Left Left case, else Right Left case.
 If balance factor is less than -1, then the current node is unbalanced and we are either
in Right Right case or Left Right case. To check whether it is Right Right case or Left
Right case, get the balance factor of right subtree. If the balance factor of the right
subtree is smaller than or equal to 0, then it is Right Right case, else Left Right case.
/* DECLARING AVL NODE */

struct AvlNode
{
int element;
struct AvlNode *left;
struct AvlNode *right;
int height;
};
/* CALCULATING HEIGHT OF TREE*/
int height(struct AvlNode *P)
{
if (P==NULL)
return -1;
else
return P->height;
}
/* INSERTION */
struct AvlNode* Insert(int x, struct AvlNode *temp)
{
if (temp==NULL)
{
temp=malloc(sizeof(struct AvlNode));
temp->element=x;
temp->left=temp->right=NULL;
temp->height=0;
}
else
if ( x < temp->element )
{
temp->left = Insert(x, temp->left);
if (height(temp->left) - height(temp->right)==2)
if (x<temp->left->element)
temp=SingleRotateWithLeft(temp);
else
temp=DoubleRotateWithLeft(temp);
}
else if ( x>temp->element )
{
temp->right = Insert(x, temp->right);
if (height(temp->right) - height(temp->left)==2)
if (x > temp->right->element)
temp=SingleRotateWithRight(temp);
else
temp=DoubleRotateWithRight(temp);
}
/*else x is already in the tree*/
temp->height = max(height(temp->left),height(temp->right))+1;
return temp;
}
struct AvlNode *SingleRotateWithLeft(struct AvlNode *k2)
{
struct AvlNode *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left),height(k2->right))+1;
return k1;
}
struct AvlNode* SingleRotateWithRight(struct AvlNode *k2)

{
struct AvlNode *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
return k1;
}
struct AvlNode* DoubleRotateWithLeft(struct AvlNode *k3)

{
/*Rotate between k1 and k2*/
k3->left = SingleRotateWithRight(k3->left);
return (SingleRotateWithLeft(k3));
}
struct AvlNode* DoubleRotateWithRight(struct AvlNode *k3)

{
k3->right = SingleRotateWithLeft(k3->right);
return SingleRotateWithRight(k3);
}
/* DISPLAY OPERATION*/
display(struct AvlNode *temp)
{
if (temp!=NULL)
{
printf("%5d",temp->element);
preorder(temp->left);
preorder(temp->right);
}
}
/* SEARCH OPERATION*/
void find(int key, struct AvlNode *temp)
{
if(temp==NULL)
{
printf("\nElement Not found");
return;
}
else if(temp->element==key)
{
printf("\nElement found");
return;
}
else if(key < temp->element)
find(key, temp->left);
else
find(key, temp->right);
}

Unit-4 3

Uploaded by

Copyright:

Available Formats

Unit-4 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit-4 3

Uploaded by

Copyright:

Available Formats

AVL Trees

The balance factor bf(x) of a node is defined as,

bf(x) = height of left sub-tree of x – height of right subtree of x

Height of an AVL Tree:

Different Rotations in AVL tree:

a) LL Rotation: (Left Left Case )

 Delete the node using BST deletion procedure.

/* DECLARING AVL NODE */

struct AvlNode* SingleRotateWithRight(struct AvlNode *k2)

struct AvlNode* DoubleRotateWithLeft(struct AvlNode *k3)

struct AvlNode* DoubleRotateWithRight(struct AvlNode *k3)

You might also like