3.23

Algorithm
Let
  lowerBound(p) = first key ≥ p in the tree (standard search),
  successor(x) = in-order successor of node x.

printPrefix(p):
  x ← lowerBound(p) // O(l log n)
  while x ≠ null and x.key.startsWith(p):
    output x.key // report string
    x ← successor(x) // O(l log n) each


Correctness
The dictionary is kept in lexicographic order. All strings beginning with p lie consecutively between p itself and the smallest string that is greater than every p-prefix string. lowerBound(p) reaches the first element of this block; repeatedly taking successor walks through the block until a key no longer starts with p, thus printing exactly the desired strings.

Complexity
• One key comparison inspects at most l characters.
• lowerBound touches O(log n) nodes ⇒ O(l log n).
• Each of the m iterations calls successor, which again uses O(log n) comparisons ⇒ O(ml log n).
• Outputting the m strings costs O(ml) and is subsumed.
Hence the overall running time is [math]\displaystyle{ O(ml\log n) }[/math] with only O(1) extra space.

Back to Chapter 3