Neeraj's Blog

There is always an open source solution..

AVL Tree

AVL tree is an interesting data structure invented by G.M Adelson-Velskii and E.M.Landis. It is a self balancing binary tree. Self balancing means doing some operations, the tree tries to keep its height as low as possible. Most operations on a binary search tree (BST) take time directly proportional to the height of the tree, so it is desirable to keep the height small.

In an avl tree the height of the two sub trees differ at most one. 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. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree.

Now we can try to analyse insertion function of an avl tree. If we can write an insertion function we can also write look up function also.

Inserting into an avl tree is same as the insertion into an ordinary bst. But after inserting an element we have to make sure that the tree is balanced. If the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes ±2 then the subtree rooted at this node is unbalanced.

There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree, with R and L denoting the right and left children of P respectively.

Right-Right case and Right-Left case:

  • If the balance factor of P is -2 then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. The left rotation with P as the root is necessary.
  • If the balance factor of R is -1, a single left rotation(with P as the root) is needed (Right-Right case).
  • If the balance factor of R is +1, two different rotations are needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root (Right-Left case).

Left-Left case and Left-Right case:

  • If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. The right rotation with P as the root is necessary.
  • If the balance factor of L is +1, a single right rotation(with P as the root) is needed (Left-Left case).
  • If the balance factor of L is -1, two different rotations are needed. The first rotation is a left rotation with L as the root. The second is a right rotation with P as the root (Left-Right case).

Pictorial description of how rotations cause rebalancing tree, and then retracing one's steps toward the root updating the balance factor of the nodes. The numbered circles represent the nodes being balanced. The lettered triangles represent subtrees which are themselves balanced BSTs

The c code implementation of avltree can get from https://bitbucket.org/neeraj_r/data-structures/changeset/2adb14b6ffa5

Single Post Navigation

One thought on “AVL Tree

  1. Nice explanation!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: