AVL Tree

AVL Tree, named after its inventors Adelson-Velskii and Landis, is a self-balancing binary search tree that maintains the height balance property (in addition to the BST order property) using structural rotations.

The insertion and deletion operations for AVL trees begin similarly to the corresponding operations for (regular) binary search trees. It then performs post-processing structural rotations to restore the balance of any portions of the tree that are adversely affected by the insertion/removal.

Insertion

  • Insert item as in binary search tree.
  • Starting with new node, go up to update heights.
  • If find a node that has become unbalanced, do rotation to rebalance.
  • Rebalance reduces height of sub-tree by $1$, so no need to propagate up – only one adjustment needed at most because it was previously balanced before the insert.
  • So, in total, $O(\lg N)$ to insert and $O(1)$ to rebalance.

Removal

  • Remove item as in binary search tree.
  • Starting with the parent of the deleted node, go up to update heights.
  • By "deleted node," I mean the actual deleted node (which is going to be a leaf) not the node which its value was replaced with in-order predecessor/successor.
  • As you go up from the deleted node to update the heights of its ancestors, rebalance them as needed (perform rotation).
  • Rotations may reduce the height of a subtree, causing further imbalances for ancestors, so you may need to perform more than one rebalancing operation.
  • Since you travel from the deleted node upwards to the root, at most you will perform $O(\lg n)$ rotations.
  • So, in total, $O(\lg n)$ to remove and $O(\lg n)$ to rebalance.

Recommendation: Implement insertion/removal (with structural rotations) recursively!

For the implementation of AVL Tree, you must store the height of each node.

As you insert/remove, you must travel upward towards the root to update the height of ancestors.

Resources