Augmentation: Improve an existing data structure for a specific problem (e.g. AVL trees augment BSTs)

• Add new info on top
• Adjust original operations to keep new info up-to-date
• Implement new operations

Ordered Set ADT

Objects: Set of comparable elements, no duplicates

Operations: SEARCH, INSERT, DELETE, RANK, SELECT

• RANK(x): Return the rank k of x (the k-th smallest is x) (smallest = rank 1)
• SELECT(k): Return the element of rank k

Ordered Set: Augmented AVL

Additional Info: Store size of each subtree in its node

Operations:

• INSERT: Do a regular AVL insert, then increase size by 1 from the inserted node up to its root
• DELETE: Do a regular AVL delete, then decrease size by 1 from the parent up to the root
  • ROTATE: Recalculate rotated nodes
• RANK(x): Search for x, keep track of current rank r
  1. When recursing left, no change to r
  2. When recursing right, r += 1 + left.size
  3. Found x, return r + 1 + left.size
• SELECT(k): Start at root, r = 1 + left.size
  1. If k < r, recurse left
  2. If k > r, recurse right with r = k - r
  3. If k = r, return root