gpt4 book ai didi

algorithm - 范围树实现

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:23:00 24 4
gpt4 key购买 nike

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

enter image description here

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

enter image description here

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

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

最佳答案

不久前,我实现了维基百科 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)),因此它应该相当高效也是。

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

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

关于algorithm - 范围树实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30497728/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com