Archived Content

This website is an archive of the Spring 2019 semester of CS 225.
→ Click here to view the current semester.
Back to Notes

AVL Trees

by Eddie Huang

A Cool Demo

Interactive AVL Simulator

Description

AVL Trees are self-balancing binary search trees that allow you to store and query data in logarithmic time. They maintain a logarithmic height so that functions like find and insert take logarithmic time. Whenever any node has an imbalance of 2 or greater, the tree performs rotations to rebalance.

The imbalance of a node in a binary tree is defined as the height difference between its two subtrees.

If an AVL tree has multiple imbalanced nodes, it will rebalance the nodes from the lowest level to the highest.

A left rotation

1: Unbalanced Tree
2: Left rotation

Right rotations and left rotations are mirrors of each other.

A right-left rotation

1: Unbalanced Tree
2: Right rotation
3: Left rotation

Left-right rotations and right-left rotations are mirrors of each other.