algorithm - 范围树实现

Question

我正在尝试实现一个范围树，但我真的很困惑，这是我的文字:

现在假设我有一棵这样的树:

我想找到 14 和 19 之间的点。V_Split 这里是 17，从 17 移动到 14，根据算法，我应该报告 17 的右子树是23和19。但是23不在14和19之间。我该怎么办？

如果我不考虑 17，那么 17 本身就不会被报告。然后如果我想找到 12 和 19 之间的点，14 将不会被包括在内!

Answer 1

不久前，我实现了维基百科 Range Tree 中描述的步骤文章(范围查询部分)，这些看起来与您的文字相似。主要思想是找到 vsplit 点，然后二分搜索 vsplit 的左右子节点，在我们移动时获取所有“在范围内”的节点。

我想让数据结构 (TreeNode) 保持真正的基本，以便于理解(因为我没有看到需要像文章建议的那样将每个节点存储为叶子？)。无论如何，您可以在下面找到我的类的主要方法，它包含逐步解释的总体思路。欢迎从我的 github repository 中获取完整代码但我建议先尝试自己编写 getLeftNodes()/getRightNodes() 代码。

    /**
     * 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;
    }

此实现的时间复杂度目标应为 O(log(n))，因为我们正在进行三个二进制搜索(vsplit + 左 + 右)，每个搜索都采用 O(log(n))，因此它应该相当高效也是。

编写此代码有助于我理解范围树的一般概念(在代码挑战中非常有用)，我希望它对你也有同样的作用。

注意:我确信还有更简单的实现(和更高效的实现)!