Range tree implementation

Question

I'm trying to implement a Range tree but I'm really confused, Here is my text:

Now suppose that I have a tree like this:

And I want to find the points between 14 and 19. V_Split would be 17 here, and moving from 17 to 14, according to algorithm, I should report the right sub-tree of 17 that is 23 and 19. But 23 is not between 14 and 19. What should I do here?

If I dont consider 17, then 17 itself wont be reported. And then again if I want to find the points between 12 and 19, 14 wont be included!

Answer 1

A while ago I implemented the steps described at the Wikipedia's Range Tree article (Range queries section), these look like similar to your text. The main idea is to find the vsplit point and then binary search vsplit's left and right childs, grabing all the "in range" nodes as we move.

I wanted to keep the data structure (TreeNode) really basic to make it easier to understand (since I didn't saw the need to store every node as leafs as the article suggests?). Anyway, below you can find the main method for my class, it contains the general idea explained step by step. Feel free to grab the entire code from my github repository but I would suggest trying to code getLeftNodes()/getRightNodes() by yourself first.

/**
 * Range trees can be used to find the set of points that lay inside a given
 * interval. To report the points that lie in the interval [x1, x2], we
 * start by searching for x1 and x2.
 * 
 * The following method will use a regular balanced binary search tree for
 * this purpose. More info in https://en.wikipedia.org/wiki/Range_tree
 * 
 * @param x1
 *            Low (start) range position
 * @param x2
 *            High (end) range position
 * @param root
 *            A balanced binary search tree root
 * @return
 */
public HashSet<Integer> getNodesInRange(int x1, int x2, TreeNode root) {
    if (x1 >= x2) {
        throw new IllegalArgumentException("Range error: x1 must be less than x2");
    }

    // At some vertex in the tree, the search paths to x1 and x2 will
    // diverge. Let vsplit be the last vertex that these two search paths
    // have in common.
    TreeNode vsplit = root;
    while (vsplit != null) {
        if (x1 < vsplit.data && x2 < vsplit.data) {
            vsplit = vsplit.left;
        } else if (x1 > vsplit.data && x2 > vsplit.data) {
            vsplit = vsplit.right;
        } else {
            break;
        }
    }

    // Report the value stored at vsplit if it is inside the query interval.
    HashSet<Integer> nodesInRange = new HashSet<>();
    if (vsplit == null) {
        return nodesInRange;
    } else if (inRange(vsplit.data, x1, x2)) {
        nodesInRange.add(vsplit.data);
    }

    // Continue searching for x1 in the range tree (vSplit to x1).
    getLeftNodes(x1, x2, nodesInRange, vsplit.left);
    // Continue searching for x2 in the range tree (vSplit to x2).
    getRightNodes(x1, x2, nodesInRange, vsplit.right);

    return nodesInRange;
}

The time complexity target for this implementation should be O(log(n)) since we are doing three binary searches (vsplit + left + right) taking O(log(n)) on each one so it should be decently efficient too.

Coding this helped me understand the range tree general idea (very useful in code challenges) and I hope it does the same for you.

Note: I'm sure there are even easier implementations (and more efficient ones) out there!