What is an AVL tree?

Add comment

Votes: 0

Comments: 0

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion and lookup times. AVL trees overcome this problem.

An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.

Balance factor of each node = height of right subtree at that node - height of left subtree at that node.

Here is some recursive C code that sets the Balance factor for all nodes starting from the root....

setbf(mynode *p)
{
int count;

count = 1;

if(p == NULL)
{
return(0);
}
else
{
templ = setbf(p->left);
tempr = setbf(p->right);

if(templ < tempr)
count = count + tempr;
else
count = count + templ;
}

// Set the nodes balancing factor.
p->bf = tempr - templ;

return(count);
}

After insertion, the tree might have to be readjusted as needed in order to maintain it as an AVL tree. A node with balance factor -2 or 2 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, possibly stored at nodes. If, due to an instertion or deletion, the tree becomes unbalanced, a corresponding left rotation or a right rotation is performed on that tree at a particular node. A balance factor > 1 requires a left rotation (i.e. the right subtree is heavier than the left subtree) and a balance factor < -1 requires a right rotation (i.e. the left subtree is heavier than the right subtree).

Here is some pseudo code to demonstrate the two types of rotations...

Left rotation

BEFORE

0 (par)

0 0 (p)

0 0 (tmp)

0 0 0 0
(a) (b)

Here we left rotate the tree around node p

tmp = p->right;
p->right = tmp->left;
tmp->left = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Reclaculate the balance factors
setbf(root);

AFTER
0 (par)

0 0
(tmp)

0 0
(p) (b)

0 0
(a)

0 0

Right rotation

BEFORE

0 (par)

0 0 (p)

0 (tmp) 0

0 0 0 0
(a) (b)

Here we right rotate the tree around node p

tmp = p->left;
p->left = tmp->right;
tmp->right = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Recalculate the balancing factors...
setbf(root);

AFTER

0 (par)

0 0 (tmp)

0 0
(a) (p)

0 0
(b)

0 0

Others in this Category

	What is a threaded binary tree?
	Q: Is BETWEEN inclusive of the range values specified?
	Q: When do you use a LIKE statement?
	Q: What is the meaning of underscore ( ‘_’ ) in the LIKE statement?
	Q: 6. What do you accomplish by GROUP BY .... HAVING clause?
	Write a C program to count bits set in an integer?
	Find the closest ancestor of two nodes in a tree.
	Q: What are the contents of a DCLGEN?
	Write pseudocode to add a new node to a Binary Search Tree (BST)
	What is a threaded binary tree?
	» More articles