A binary search tree (BST) stores keys so that for every node N:

  • All keys in the left subtree are < N.key.
  • All keys in the right subtree are > N.key.

Lookup, insert and delete are O(h) where h is the height. In the worst case (inserting a sorted sequence), an unbalanced BST degenerates into a linked list with h = n, making everything O(n).

A balanced BST keeps h = O(log n) no matter the insertion order. The two famous designs are:

  • AVL tree — strictly balanced (height difference between sibling subtrees ≤ 1). Slightly faster lookups, more rotations on insert/delete.
  • Red-black tree — loosely balanced. Used by std::map in C++ and Java's TreeMap. Fewer rotations, slightly deeper tree.

We implement an AVL tree because the rebalancing logic is short and easy to reason about.

AVL invariant

For every node, |height(left) - height(right)| ≤ 1. After every insert or delete, restore the invariant with rotations.

balance(n) = height(n.left) - height(n.right)

if balance > 1 and key < n.left.key       -> Right rotation         (LL)
if balance < -1 and key > n.right.key     -> Left rotation          (RR)
if balance > 1 and key > n.left.key       -> Left-Right rotation    (LR)
if balance < -1 and key < n.right.key     -> Right-Left rotation    (RL)

Rotations

Right rotation around y:

       y                     x
      / \                   / \
     x   T3   ----->       T1  y
    / \                       / \
   T1 T2                     T2 T3

Both rotations are O(1).

Operations and complexity

Op Time
Insert O(log n)
Search O(log n)
Delete O(log n)
In-order traversal O(n)

What we implement

avl.Tree[T avl.Ordered] with:

  • Insert(key T)
  • Contains(key T) bool
  • Delete(key T) bool
  • Len() int
  • InOrder() []T — sorted snapshot
  • Height() int — height of the tree

Tests check correctness against sort.Sort and verify the balance invariant after random operations.

Run the tests

go test ./part2-dsa/ds/avl