AVL Trees

bst

Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary search tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor (Tutorialspoint, n.d.).

To balance itself, an AVL tree may perform the following four kinds of rotations −

  • Left rotation
  • Right rotation
  • Left-Right rotation
  • Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let’s understand them one by one.

References

Tutorialspoint. (n.d.). Data Structure and Algorithms – AVL Trees. Tutorialspoint. Retrieved from: https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm