Oldest Self-Balancing Binary Search Tree invented

AVL Tree

Learned in CS240.

An AVL Tree is a BST with an additional height-balance property at every node:

Important

The height of an empty tree is defined to be .

If node has left subtree and right subtree , then

  • means is left-heavy
  • means is right-heavy

Theorem

An AVL tree on nodes has height. search, insert, delete all cost in the worst case!

In the case of ties

VERY IMPORTANT: Ties must be broken to prefer single rotation. There are scenarios where if we don’t prefer the single rotation, applying double rotation does not result in a valid AVL tree afterwards.

  • Note here: the parent here on line 2 refers to the parent of the node with value after the swap. Like in the example below, calling delete 22, we get the min key of the right subtree, do the swap, and then the parent will be the node with key .

AVL Tree Operations Runtime