What is an AVL tree?

The primary issue with binary search trees is that they can be unbalanced. In the worst case, they are still not more efficient than a linked list, performing operations such as insertions, deletions, and searches in $O(n)$ time.

AVL trees are a modification of binary search trees that resolve this issue by maintaining the balance factor of each node.

Balance Factor

The balance factor of a node is the difference in the heightThe length of the path from the root node to the tree's deepest descendant. of the left and right sub-tree. The balance factor of every node in the AVL tree should be either +1, 0, or -1. In other words, AVL trees are binary search trees that maintain the following height-balance property for all nodes $N$:

Each time a node is inserted into an AVL tree or deleted from an AVL tree, the balance factor of a node(s) may be disrupted (it will lie outside the range [-1, 1], which causes the AVL tree to become unbalanced). The examples below demonstrate this:

Types of imbalances

Four types of imbalances can occur in an AVL tree via the insertion or deletion of a node(s). These are:

To deal with each type of imbalance and fix it, AVL trees can perform rotations. These rotations involve switching around positions of the unbalanced node's sub-tree(s) to restore the balance factor of all affected nodes.

By maintaining this balancing factor for each node, AVL trees allow the primary operations of a binary search tree (insert, delete, search) to run efficiently in $O(log(n))$ time in the worst case.