algorithm - 为什么从范围树查询中获得的子树的数量是 O(log(n))？

Question

我试图弄清楚这个数据结构，但我不明白我们怎么知道有 O(log(n)) 子树代表查询的答案？

这是一张用于说明的图片：

谢谢！

标签： algorithmdata-structurestreerange-tree

Answer 1

考虑搜索范围的两个端点。此搜索将继续，直到找到跨越您的区间的两个叶节点的最低共同祖先。那时，搜索分支，一部分向左弯曲，一部分向右弯曲。现在，让我们只关注向左分支的查询部分，因为逻辑相同，但右分支的逻辑相反。

在此搜索中，将每个节点视为不代表单个点，而是代表一系列点会有所帮助。那么，一般程序如下：

1. 如果查询范围完全包含该节点表示的范围，则停止在 x 中搜索并开始搜索该节点的 y 子树。

2. 如果查询范围纯粹在该节点的右子树表示的范围内，则继续向右搜索 x 并且不调查 y 子树。

3. 如果查询范围与左子树的范围重叠，则它必须完全包含右子树的范围。所以处理右子树的y子树，然后递归地探索左边的x子树。

在所有情况下，我们最多添加一个 y 子树以供考虑，然后仅在一个方向上递归地继续探索 x 子树。这意味着我们基本上沿着 x-tree 追踪一条路径，每一步最多添加一个 y-subtree。由于树的高度为 O(log n)，因此以这种方式访问​​的 y 子树的总数为 O(log n)。然后，包括在我们在顶部分支的情况下访问的 y 子树的数量，我们得到另一个 O(log n) 子树，总共 O(log n) 个子树要搜索。

希望这可以帮助！