The code in the IM is broken. Here is the fixed version (line 8 were missing):
OS-Select(x, i)
1 r = x.left.size + 1
2 while i != r
3 if i < r
4 x = x.left
5 else
6 x = x.right
7 i = i - r
8 r = x.left.size + 1
9 return x
17.1-4
Available in the latest revision of the IM.
17.1-5
Available in the latest revision of the IM.
17.1-6
Available in the latest revision of the IM.
To text in the IM contains a completely redundant sentence "Similarly when deleting, subtract 1 from x:rank whenever the spliced-out node had been in x’s left subtree." Because it starts with "Similarly...", it reads as if it is introducing a new rule or handling an edge case. In reality, it is just repeating the exact logic that the previous paragraphs already covered.
17.1-7
Available in the latest revision of the IM.
★ 17.1-8
Available in the latest revision of the IM.
17.2-1 🌟
Demonstrates an interesting approach of creating a hybrid data structure consisted of a doubly linked list and an augmented order-statistic tree, which nicely interplay to support all operations efficiently. For example, a tree may help quickly locate the corresponding node based on a key value, while a linked list may provide additional information (like, successor) in O(1) time.
Available in the latest revision of the IM.
17.2-2
Available in the latest revision of the IM.
17.2-3
Available in the latest revision of the IM.
17.3-1
Available in the latest revision of the IM.
17.3-2
Available in the latest revision of the IM.
The function Min-Interval-Search-From unconditionally branches to x.right in the last line even if it is T.nil. Furthermore, it assumes that x is not T.nil. An easy fix is to simply insert a test in line 1 whether x is T.nil and return T.nil if positive.
17.3-3
The non-modifying version of the pseudocode follows the structure of the solution from the previous exercise. An ordinary inorder traversal of a tree would entail a Θ(n) runtime. Leveraging additional information stored in nodes we can make informed decisions whether to descend into branches. This reduces the running time as given in the book. There is only one caveat, that an unsuccessful search also consumes time, so for k=0 we don't have a zero time.
17.3-4
First, we must modify the tree's insertion procedure to use int.high as a secondary key.
If i.low < x.int.low, go left.
If i.low > x.int.low, go right.
If i.low == x.int.low, compare i.high and x.int.high to decide whether to go left or right (see below).
Leaving the max attribute and the standard overlap logic completely untouched means all our existing operations—like regular interval search—work as before.
With the above modification, an interval tree can be regarded as an ordinary BST for exact search.
17.3-5
Available in the latest revision of the IM.
★ 17.3-6
Available in the latest revision of the IM.
Problems
17-1 Point of maximum overlap
Available in the latest revision of the IM.
17-2 Josephus permutation
Available in the latest revision of the IM.
The modular arithmetic to compute the next rank j is as follows:
j = (j + m - 1) mod k
if j == 0
j = k
The IM employs a neat trick to condense all this into a one-liner: j = ((j + m - 2) mod k) + 1. The idea is to first shift the whole domain down by subtracting -1. The modulo operator safely wraps the value within the range [0,k−1]. Adding 1 shifts the result back to the desired [1,k] range.
All-Interval-Search(T, i)
1 out = a new empty linked list
2 All-Interval-Search-From(T, T.root, i, out)
3 return out
All-Interval-Search-From(T, x, i, out)
1 if x != T.nil
2 // Search the left subtree if it can possibly contain overlaps.
3 if x.left != T.nil and x.left.max >= i.low
4 All-Interval-Search-From(T, x.left, i, out)
5
6 // Check if the current node's interval overlaps i.
7 if x.int.low <= i.high and x.int.high >= i.low
8 List-Insert(out, x.int)
9
10 // Search the right subtree if it can possibly contain overlaps.
11 // We only go right if x.int.low <= i.high (since right children
12 // have even greater low endpoints) and the right subtree's max >= i.low.
13 if x.right != T.nil and x.int.low <= i.high and x.right.max >= i.low
14 All-Interval-Search-From(T, x.right, i, out)
Interval-Search-Exactly(T, i)
1 x = T.root
2 while x != T.nil
3 if i.low == x.int.low and i.high == x.int.high
4 return x
5 if i.low < x.int.low or (i.low == x.int.low and i.high <= x.int.high)
6 x = x.left
7 else
8 x = x.right
9 return T.nil
