AVL Trees

An AVL Tree is a self balancing binary search tree (BST). It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. The height of an AVL sub-tree can differ at most by 1. This allows us to search for an element in the AVL tree in log base 2 n time or O(log n), where n is the number of elements in the tree. As a matter of fact this allows for operations such as max, min, insertion, and deletion to all be O( log n).

AVL Tree Insertion

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1.

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

BalanceFactor(N) = Height(RightSubtree(N) ) — Height(LeftSubtree(N))
or
BalanceFactor(N) = Height(LeftSubtree(N)) — Height(RightSubtree(N) )

BalanceFactor(N) belongs to the set {-1,0,1}