AVL Trees

What is an AVL Tree?

An AVL tree is a self-balancing binary search tree. It is named after inventors Adelson-Velsky and Landis. The tree automatically keeps itself balanced to ensure fast operations.

Key Properties

AVL trees have many important properties:

Each node has a balance factor of -1, 0, or 1
The tree automatically rebalances after insertions and deletions
All operations take O(log n) time in the worst case

Rotations

AVL trees use rotations to stay balanced. There are four types:

Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation

Visual Example

An AVL tree showing balance factors at each node.

Learn More

For more information about AVL trees:

AVL Tree Tutorial on GeeksforGeeks