Order-Stastics Tree and Interval Trees (by augmenting RBTs)

[nbro]

References

• Chapter 14 of "Introduction to algorithms" by CLRS to augment the RBT ds.

• Slides by prof. Papadopoulou

---

The BST has a rank method, which works in linear time instead of the possible optimal logarithmic time...

Add support for:

• Order statistics tree (OS-RANK, OS-SELECT) in log(n) time by augmenting the RBT with a field called size to each node x, which represents the number of nodes under x. This field must be maintained though.

• Add support for interval trees

---

Order Statistics Tree

The OS-SELECT(T, i) (returns the ith element in T) method could look like this:

OS-SELECT(T, i): // we're looking for the ith smallest element in T
    OS-SELECT-AUX(T.root, i) // we start from the root

OS-SELECT-AUX(x, i):
    r = x.left.size + 1 // x.left.size because the elements on the left precede x
    if r == i: // x is at the ith position 
        return x
    else if i < r: // search in the left subtree of x
        return OS-SELECT-AUX(x.left, i)
    else:  // i >= r
        // since the subtree rooted at x contains r elements
        // that come before x's right subtree in a inorder tree walk
        // the ith smallest element in the subtree rooted at x
        // is the (i - r) element rooted at x's right subtree.
        return OS-SELECT-AUX(x.right, i - r)

The OS-RANK(T, x) (the number of elements that precede x in an inorder tree walk of T + 1, to account for x itself) that instead could look like this:

OS-RANK(T, x):
    r = x.left.size + 1
    y = x
    while y != T.root:
        // if y is a right child
        // then both its parent and all the nodes in its parent's left subtree
        // come before y in a inorder tree walk of T 
        if y == y.parent.right: 
            r = r + y.parent.left.size + 1
        y = y.parent
    return r

We need to maintain the field size when the RBT is modified during insertions and deletions. During insertions, when we go down through the path until the position of the new node, we increase the size of all nodes in these path by 1. Going up, to the fix the height of the tree to maintain it balanced, we do at most 2 rotations. During these rotations we also need to change the sizes of the nodes involved only in the rotation, since the rotation is a local operation. For example, in a left-rotate, we could do something like this (omitting handling of nil s and parent points):

VERIFY THAT THIS PSEUDOCODE IS CORRECT!!!

OS-LEFT-ROTATE(T, x):
    y = x.right
    x.right = y.left
    y.left.parent = x
    ...

    // the size of y becomes the size of its parent x
    y.size = x.size 

    // the new size of x is the sum of the sizes of its two 
    x.size = x.left.size + x.right.size + 1 children + 1
    ...

During deletion, we do at most 3 rotations. When going up doing these rotations, we need also to decrease the size of the nodes all the way up to the root.

We can also implement easily other operations such as OS-ITH-SUCCESSOR, OS-ITH-PREDECESSOR by simply combining OS-RANK and OS-SELECT. For example OS-ITH-SUCCESSOR(T, x, i) can be implemented as follows:

OS-ITH-SUCCESSOR(T, x, i):
    r = OS-RANK(x)
    return OS-SELECT-AUX(T.root, r + i) // select the (r + i)th element from the tree

OS-ITH-PRECESSOR can be implemented similarly by passing as second parameter to OS-SELECT-AUX r - i.

All the operations we have mentioned so far run all in O(log n).

Interval Trees

Idea: store intervals in the nodes of a RBT organized according to the low values of the intervals. In addition, augment the RBT's nodes with a field max which is the maximum value of the subtree rooted at that corresponding node, i.e.

x.max = max(x.interval.high, x.left.max, x.right.max)

We need to maintain this new field max during insertions and deletions. But this can be easily achieved, since this is a local information.

The INTERVAL-SEARCH procedure looks like this:

INTERVAL-SEARCH(T, i):
x = T.root
while x != T.nil and i does not overlap x:
    if x.left != T.nil and (x.left.max >= i.low):
        x = x.left // move left if the maximum key in the left subtree is greater than i.low
    else:
        x = x.right
return x

Other operations that could be useful are:

1. INTERVAL-SEARCH-EXACTLY (Check solutions to 2nd homework of ans2).

2. INTERVAL-SEARCH-ALL(T, i), which searches all intervals in T which overlap the interval i. This operation can be implemented by imitating the deletion of a found overlapping interval. (Check solutions to 2nd homework of ands2).