14.1 Dynamic order statistics

14.1-1

Show how $\text{OS-SELECT}(T.root, 10)$ operates on the red-black tree $T$ of Figure 14.1.

  • $26: r = 13, i = 10$, go left.
  • $17: r = 8, i = 10$, go right.
  • $21: r = 3, i = 2$, go left.
  • $19: r = 1, i = 2$, go right.
  • $20: r = 1, i = 1$, choose $20$.

14.1-2

Show how $\text{OS-RANK}(T, x)$ operates on the red-black tree $T$ of Figure 14.1 and the node $x$ with $x.key = 35$.

  • $35: r = 1$.
  • $38: r = 1$.
  • $30: r = r + 2 = 3$.
  • $41: r = 3$.
  • $26: r = r + 13 = 16$.

14.1-3

Write a nonrecursive version of $\text{OS-SELECT}$.

1
2
3
4
5
6
7
8
9
OS-SELECT(x, i)
    r = x.left.size + 1
    while r != i
        if i < r
            x = x.left
        else x = x.right
            i = i - r
        r = x.left + 1
    return x

14.1-4

Write a recursive procedure $\text{OS-KEY-RANK}(T, k)$ that takes as input an order-statistic tree $T$ and a key $k$ and returns the rank of $k$ in the dynamic set represented by $T$. Assume that the keys of $T$ are distinct.

1
2
3
4
5
6
OS-KEY-RANK(T, k)
    if k == T.root.key
        return T.root.left.size + 1
    else if T.root.key > k
        return OS-KEY-RANK(T.left, k)
    else return T.root.left.size + 1 + OS-KEY-RANK(T.right, k)

14.1-5

Given an element $x$ in an $n$-node order-statistic tree and a natural number $i$, how can we determine the $i$th successor of $x$ in the linear order of the tree in $O(\lg n)$ time?

The desired result is $\text{OS-SELECT}(T, \text{OS-RANK}(T, x) + i)$. This has runtime $O(h)$, which by the properties of red black trees, is $O(\lg n)$.

14.1-6

Observe that whenever we reference the size attribute of a node in either $\text{OS-SELECT}$ or $\text{OS-RANK}$, we use it only to compute a rank. Accordingly, suppose we store in each node its rank in the subtree of which it is the root. Show how to maintain this information during insertion and deletion. (Remember that these two operations can cause rotations.)

First perform the usual BST insertion procedure on $z$, the node to be inserted. Then add $1$ to the rank of every node on the path from the root to $z$ such that $z$ is in the left subtree of that node. Since the added node is a leaf, it will have no subtrees so its rank will always be $1$.

When a left rotation is performed on $x$, its rank within its subtree will remain the same. The rank of $x.right$ will be increased by the rank of $x$, plus one. If we perform a right rotation on a node $y$, its rank will decrement by $y.left.rank + 1$. The rank of $y.left$ will remain unchanged.

For deletion of $z$, decrement the rank of every node on the path from $z$ to the root such that $z$ is in the left subtree of that node. For any rotations, use the same rules as before.

14.1-7

Show how to use an order-statistic tree to count the number of inversions (see Problem 2-4) in an array of size $n$ in time $O(n\lg n)$.

The runtime to build a red-black tree is $O(n\lg n)$, so we need to calculate inversions while building trees.

Every time $\text{INSERT}$, we can use $\text{OS-RANK}$ to calculate the rank of the node, thus calculating inversions.

14.1-8 $\star$

Consider $n$ chords on a circle, each defined by its endpoints. Describe an $O(n\lg n)$-time algorithm to determine the number of pairs of chords that intersect inside the circle. (For example, if the $n$ chords are all diameters that meet at the center, then the correct answer is $\binom{n}{2}$.) Assume that no two chords share an endpoint.

Sort the vertices in clock-wise order, and assign a unique value to each vertex. For each chord its two vertices are $u_i$, $v_i$ and $u_i < v_i$. Add the vertices one by one in clock-wise order, if we meet a $u_i$, we add it to the order-statistic tree, if we meet a $v_i$, we calculate how many nodes are larger than $u_i$ (which is the number of intersects with chord $i$), and remove $u_i$.