Recent Posts

AVL Tree

Written by

Sonal Moga

What is an AVL Tree ?

The AVL tree was developed by Adelson, Velskii, and Landi, hence it was named after them. An AVL tree is also a self-balancing binary search tree.

In an AVL tree, the heights of two child subtrees of any node differ by at most one; therefore it is called to be the height-balanced tree.

The operations like lookup, insertion, the deletion takes place in O (Log n) time. It is in both the average and the worst-case guarantees, where n is the number of the nodes in the tree before the operation.

The AVL Tree is very often compared to the Red-Black tree since they have a similar set of operations performed on them and also takes similar O (Log n) time for the operations.

It is a special type of Balanced Factor that must be -1, 0 or +1 for each node. The balanced factor will be calculated as,

# The basic operations of an AVL Tree

The basic operations performed on an AVL Tree is similar to that carried on an unbalanced BST, but it is preceded or followed by one or more operations called tree rotations that help restore the balance of the tree.

  1. Look Up: this operation is performed in exactly a similar way as in an unbalanced tree. Since the tree has height balancing, it takes O (Log n) time. The structure of the tree is not modified by lookups; hence there is no need for any special case or provision.
  2. Insertion: Insertion in an AVL tree may be carried out by inserting the given value into the tree as if it were an unbalanced binary search tree and retracing one’s steps toward the root updating the balance factor of the nodes.
    • If the balance factor becomes -1, 0, +1 then the tree is still in AVL form and no rotations are needed.
    • If the balance factor becomes -2, +2 then the tree has lost the AVL form and now balancing of the tree is required which could be at the most one or two.
  3. Deletion: 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 the right subtree (inorder successor) and remove that node. The node that replaced the removed node can have at most one subtree. After deletion, retrace the path back up the tree to the root, adjusting the balance factors as required.

The best-applied case of an AVL Tree will be where there is a need for frequent data lookup queries.

AVL Tree