Hard
Maintaining the max-endpoint field across an interval tree rotation
An interval tree (CLRS-style) is a red-black tree keyed on each interval's low endpoint, where every node x is augmented with x.max = max(x.high, x.left.max, x.right.max), the largest high endpoint anywhere in x's subtree. Overlap queries use this field to prune whole subtrees. During insertion fixup, a left rotation is performed at x, whose right child y becomes the subtree's new root. a, b, and c are arbitrary subtrees. What must the rotation do to keep every max field in the tree correct, and at what cost?
rotation.txt
before: x after: y
/ \ / \
a y x c
/ \ / \
b c a b37 of 46 in Data Structures & Algorithms