Skip to content

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?

Given an element $x$ in an $n$-node order-statistic tree $T$ and a natural number $i$, the following procedure retrieves the $i$th successor of $x$ in the linear order of $T$:

1
2
3
4
OS-SUCCESSOR(T, x, i)
    r = OS-RANK(T, x)
    s = r + i
    return OS-SELECT(T.root, s)

Since $\text{OS-RANK}$ and $\text{OS-SELECT}$ each take $O(\lg n)$ time, so does the procedure $\text{OS-SUCCESSOR}$.

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.)

When inserting node $z$, we search down the tree for the proper place for $z$. For each node $x$ on this path, add $1$ to $x.rank$ if $z$ is inserted within $x$'s left subtree, and leave $x.rank$ unchanged if $z$ is inserted within $x$'s right subtree. Similarly when deleting, subtract $1$ from $x.rank$ whenever the spliced-out node had been in $x$'s left subtree.

We also need to handle the rotations that occur during the fixup procedures for insertion and deletion. Consider a left rotation on node $x$, where the pre-rotation right child of $x$ is $y$ (so that $x$ becomes $y$'s left child after the left rotation). We leave $x.rank$ unchanged, and letting $r = y.rank$ before the rotation, we set $y.rank = r + x.rank$. Right rotations are handled in an analogous manner.

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)$.

Let $A[1..n]$ be the array of $n$ distinct numbers.

One way to count the inversions is to add up, for each element, the number of larger elements that precede it in the array:

$$\text{\# of inversions} = \sum_{j = 1}^n |Inv(j)|,$$

where $Inv(j) = \{i: i < j \text{ and } A[i] > A[j]\}$.

Note that $|Inv(j)|$ is related to $A[j]$'s rank in the subarray $A[1..j]$ because the elements in $Inv(j)$ are the reason that $A[j]$ is not positioned according to its rank. Let $r(j)$ be the rank of $A[j]$ in $A[1..j]$. Then $j = r(j) + |Inv(j)|$, so we can compute

$$|Inv(j)| = j - r(j)$$

by inserting $A[1], \ldots, A[n]$ into an order-statistic tree and using $\text{OS-RANK}$ to find the rank of each $A[j]$ in the tree immediately after it is inserted into the tree. (This $\text{OS-RANK}$ value is $r(j)$.)

Insertion and $\text{OS-RANK}$ each take $O(\lg n)$ time, and so the total time for $n$ elements is $O(n\lg n)$.

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$.