AVL Trees in Data Structures

  • AVL tree is a self-balancing binary search tree invented by G.M. Adelson-Velsky and E.M. Landis in 1962.
  • The tree is named AVL in honour of its inventors.
  • An AVL tree is a binary search tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL trees.
  • In an AVL tree, the heights of the two sub-trees of a node may differ by at most one. Due to this property, the AVL tree is also known as a height-balanced tree.
  • With each node of an AVL tree is associated a balance factor that is lefthigher, equal-height, or right-higher according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree.
  • An AVL Tree is a form of binary tree, however unlike a binary tree, the worst case scenario for a search is O(log n).
  • The AVL data structure achieves this property by placing restrictions on the difference in height between the sub-trees of a given node, and re-balancing the tree if it violates these restrictions.

Operations on AVL Trees

Searching for a Node in an AVL Tree

  • Searching in an AVL tree is performed exactly the same way as it is performed in a binary search tree.
  • Due to the height-balancing of the tree, the search operation takes O(log n) time to complete.
  • Since the operation does not modify the structure of the tree, no special provisions are required.

Inserting a New Node in an AVL Tree

  • Insertion in an AVL tree is also done in the same way as it is done in a binary search tree.
  • Nodes are initially inserted into AVL Trees in the same manner as an ordinary binary search tree (that is, they are always inserted as leaf nodes).
  • In the AVL tree, the new node is always inserted as the leaf node.
  • But the step of insertion is usually followed by an additional step of rotation.
  • Rotation is done to restore the balance of the tree.
  • After insertion, however, the insertion algorithm for an AVL Tree travels back along the path it took to find the point of insertion, and checks the balance at each node on the path.
  • If a node is found that is unbalanced (that is, it has a balance factor of either -2 or +2), then a rotation is performed (see the section below on rotations) based on the inserted nodes position relative to the node being examined (the unbalanced node).

Deleting from an AVL Tree

  • The deletion algorithm for AVL Trees is a little more complex, as there are several extra steps involved in the deletion of a node.
  • If the node is not a leaf node (that is, is has at least one child), then the node must be swapped with either it's in-order successor or predecessor (based on availability).
  • Once the node has been swapped we can delete it (and have its parent pick up any children it may have - bear in mind that it will only ever have at most one child).
  • If a deletion node was originally a leaf node, then it can simply be removed.
  • Now, as with the insertion algorithm, we traverse back up the path to the root node, checking the balance of all nodes along the path.
  • If we encounter an unbalanced node we perform an appropriate rotation to balance the node (see the section below on rotations).