AVL Trees

This page gives an introduction to AVL Trees

What is an AVL Tree?

An AVL Tree is a self balancing BST, named after its inventors Adelson-Velsky and Landis.

How does an AVL Tree balance?

An AVL Tree utilizes a balance factor, equal to the length of a nodes left subtree - the length of its right subtree.

When a node's balance factor is greater than 2, it performs one of the following rotations

• Single Right Rotation
• Single Left Rotation
• Left-Right Double Rotatation
• Right-Left Double Rotation

These rotations balance the tree by changing the depth of the subtrees around the unbalanced node, decreasing the deeper side and increasing the depth of the shallow side

Further Reading

Explore the formal definition and properties on the Wikipedia AVL Tree page.