AlgoVerse

Interval tree search

A search tree of intervals in which every node stores the largest high end in its subtree; with it, an interval overlapping a query is found in O(h).

Intervals go into a search tree ordered by their low end, and each node carries one extra field: max, the largest high end of the intervals in its subtree. Another example of augmenting a data structure (CLRS chapter 17).

Read the full explanation ↓
Input:
I 10×2 · low=22 · high=25PDF export

Ten intervals and the query 22 to 25: the left subtree's max (23) reaches 22, so we go left and find the interval 15 to 23.

  1. class Node:
  2. def __init__(self, low, high):
  3. self.key = low # the tree is ordered by the intervals' low ends
  4. self.high = high
  5. self.max = high # the largest high end in this subtree
  6. self.note = str(high) + "·" + str(high) # for the picture: "high·max"
  7. self.left = None
  8. self.right = None
  11. def interval_search(I, low, high):
  12. root = build(I)
  13. x = root
  14. while x is not None:
  15. if x.key <= high and low <= x.high:
  16. break
  17. if x.left is not None and x.left.max >= low:
  18. x = x.left
  19. else:
  20. x = x.right
  21. if x is None:
  22. return None
  23. found = [x.key, x.high]
  24. return found
  27. def build(rows):
  28. root = None
  29. for lo, hi in rows:
  30. node = Node(lo, hi)
  31. if root is None:
  32. root = node
  33. continue
  34. p = root
  35. while True:
  36. # Every node on the way down gets the new interval in its subtree.
  37. p.max = max(p.max, hi)
  38. p.note = str(p.high) + "·" + str(p.max)
  39. if lo < p.key:
  40. if p.left is None:
  41. p.left = node
  42. break
  43. p = p.left
  44. else:
  45. if p.right is None:
  46. p.right = node
  47. break
  48. p = p.right
  49. return root

Invariant: If any interval in the tree overlaps the query, one of them is in x's subtree.

Start

∅

low22
high25
found—

Local variables

low22
high25

Orange = changed in this step

I list

[16, 21][8, 9][25, 30][5, 8][15, 23][17, 19][26, 26][0, 3][6, 10][19, 20]

Call stack

  1. interval_search()line 11
Step 1 of 255
Black = go_left, go_right · Orange = key stepbuilt: 0/1 · go_left: 0/1 · go_right: 0/1 · overlap: 0/1
    Explanation

    The idea

    Intervals go into a search tree ordered by their low end, and each node carries one extra field: max, the largest high end of the intervals in its subtree. Another example of augmenting a data structure (CLRS chapter 17).

    Searching

    Two closed intervals overlap when each starts before the other ends. At each node:

    • if the node's interval overlaps the query, we are done;
    • if there is a left subtree and its max is ≥ the query's low, go left;
    • otherwise go right.

    Why it is correct

    If we went right, the left max was below low, so nothing on the left reaches the query. If we went left and the left holds no overlap, the interval that set max reaches low but starts after the query's high; every interval on the right starts later still, so the right held nothing either. So one path is enough: O(h).

    The input

    Each row of I is an interval [low, high]; low and high are the query. Under each node is "its high end · max".