AVL tree's are a type of self-balancing binary trees where each node's left and right subtrees differ in height by at most only 1. AVL trees perform their auto balancing by performing "rotations" on insertion and deletion depending on where affected nodes were/are located.

To support quick inserts and removals, AVL tree's typically store the height of each node alongside the node's data. This height is then recalculated and updated for a few specific nodes after rotations.

Imbalance

After a node is inserted or deleted from the tree it's predecessor can become "imbalanced" (the difference between the heights of it's left and right children become greater than 1).

With the assumption that the tree was balanced before an operation there can only be 4 different types of imbalance.

Left-Left Imbalance

A left-left imbalance occurs when a node’s left subtree is taller than its right subtree by more than 1, and the extra height comes from the left child’s left subtree. A left-left imbalance can be fixed by performing a single right rotation on the root node.

Example of a subtree with a left-left imbalance

Right-Right Imbalance

A right-right imbalance occurs when a node’s right subtree is taller than its left subtree by more than 1, and the extra height comes from the right child’s right subtree. A right-right imbalance can be fixed by performing a single left rotation on the root node.

Example of a subtree with a right-right imbalance

Left-Right Imbalance

A left-right imbalance occurs when a node’s left subtree is taller than its right subtree by more than 1, and the extra height comes from the left child’s right subtree. A left-right imbalance can be fixed by performing a left rotation on the left child, turning the tree into a left-left imbalance which can be resolved with a right rotation at the subtrees new root.

Example of a subtree with a left-right imbalance

Right-Left Imbalance

A right-left imbalance occurs when a node’s right subtree is taller than its left subtree by more than 1, and the extra height comes from the right child’s left subtree. A right-left imbalance can be fixed by performing a right rotation on the right child, turning the tree into a right-right imbalance which can be resolved with a left rotation at the subtrees new root.

Example of a subtree with a right-left imbalance

Rotations

Rotations are operations that can be performed on AVL tree's which change the shape of the tree while maintaining the properties of a binary search tree.

Left Rotation

Given a subtrees root with a right sub child a left rotation can be performed in the following steps:

1. Create a temporary reference to the old root's right child as temp.
2. Update the old root's right child to be temp's left child (if it exists).
3. Update temp's left child to be the old root.
4. If the old root had a parent update it's references to temp accordingly.

Right Rotation

Given a subtrees root with a left sub child a right rotation can be performed in the following steps:

1. Create a temporary reference to the old root's left child as temp.
2. Update the old root's left child to be temp's right child (if it exists).
3. Update temp's right child to be the old root.
4. If the old root had a parent update it's references to temp accordingly.