algorithm - 范围树实现

Question

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

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

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

如果我不考虑 17，则不会报告 17 本身。再说一次，如果我想找到 12 到 19 之间的点，14 将不包括在内！

Answer 1

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

我想保持数据结构（TreeNode）非常基本，以便更容易理解（因为我没有看到需要将每个节点存储为文章建议的叶子？）。不管怎样，你可以在下面找到我的类的主要方法，它包含逐步解释的一般思想。随意从我的github 存储库中获取整个代码，但我建议先尝试自己编写 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 + left + right），每个搜索都需要 O(log(n))，所以它也应该是相当有效的。

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

注意：我确信那里有更简单的实现（和更有效的实现）！