What is AVL Tree?

VietMX Staff asked 3 years ago

AVL trees are height balancing binary search tree. It is named after Adelson-Velsky and Landis, the inventors of the AVL 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. This allows us to search for an element in the AVL tree in O(log n), where n is the number of elements in the tree.

The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N))height(right_sutree(N)) // BalanceFactor(N) belongs to the set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations:

  • Left Rotation,
  • Right Rotation,
  • Left Right Rotation,
  • Right Left Rotation.

avl-tree