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!
- See Tree Rotation
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 .