2

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

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

在此处输入图像描述

谢谢！

4

2 回答 2

0

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

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

  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) 个子树要搜索。

希望这可以帮助！

于 2020-06-12T21:04:59.103 回答
0

如果我们假设上面是一个纯粹的功能二叉树 [wiki]，所以节点是不可变的，那么我们可以制作这棵树的“副本”，使得只有值大于x 1且小于x 2在树中。

让我们从一个非常简单的案例开始来说明这一点。想象一下，我们根本没有任何界限，我们可以简单地返回整个树。因此，我们不是构造一棵新树，而是返回对树根的引用。所以我们可以在没有任何界限的情况下返回O(1)中的树，因为该树没有被编辑（至少只要我们使用子树就不会）。

上面的例子当然很简单。我们只是制作整个树的“副本”（不是真正的副本，因为数据是不可变的，我们可以只返回树）。因此，让我们的目标是解决一个更复杂的问题：我们要构建一个包含所有大于阈值x 1的元素的树。基本上我们可以为此定义一个递归算法：

  1. None（或任何代表空引用或对空树的引用）的剪切版本是None；
  2. 如果节点的值小于阈值，我们返回右子树的“切割”版本；和
  3. 如果节点的值大于阈值，我们返回一个具有相同右子树的 inode，并将左子子的切割版本作为左子。

所以在伪代码中它看起来像：

def treelarger(some_node, min):
    if some_tree is None:
        return None
    if some_node.value > min:
        return Node(treelarger(some_node.left, min), some_node.value, some_node.right)
    else:
        return treelarger(some_node.right, min)

因此，该算法在O(h)中运行，h是树的高度，因为对于每种情况（第一个除外），我们递归到其中一个（不是两个）子节点，并且如果我们有一个没有节点的节点，它就会结束孩子（或者至少在我们需要切割子树的方向上没有子树）。

因此，我们不会制作树的完整副本。我们重用了旧树中的很多节点。我们只构建了一个新的“表面”，但大部分“体积”是旧二叉树的一部分。尽管树本身包含O(n)个节点，但我们最多构造O(h)个新节点。我们可以优化上述内容，假设其中一个子树的切割版本相同，我们不创建新节点。但这在时间复杂度方面甚至无关紧要：我们最多生成O(h)个新节点，并且节点总数要么小于原始数量，要么相同。

在完整树的情况下，树的高度h与O(log n)成比例，因此该算法将在O(log n)中运行。

那么我们如何生成一个包含两个阈值之间元素的树呢？我们可以轻松地将上面的内容重写为一个算法，该算法treesmaller生成一个包含所有较小元素的子树：

def treesmaller(some_node, max):
    if some_tree is None:
        return None
    if some_node.value < min:
        return Node(some_node.left, some_node.value, treesmaller(some_node.right, max))
    else:
        return treesmaller(some_node.left, max)

所以粗略地说有两个区别：

  1. 我们将条件从 更改some_node.value > min为some_node.value < max; 和
  2. 如果条件成立，我们在子孩子上递归right，如果条件不成立，我们在左边递归。

现在我们从上一个算法得出的结论也是可以应用于这个算法的结论，因为它再次只引入了O(h)个新节点，节点总数只能减少。

虽然我们可以构造一个同时考虑两个阈值的算法，但我们可以简单地重用上述算法来构造一个仅包含范围内元素的子树：我们首先将树传递给treelarger函数，然后通过 a treesmaller(或反之反之亦然）。

由于在这两种算法中，我们都引入了O(h)个新节点，并且树的高度不会增加，因此我们最多构造O(2 h ) 个新节点，从而构建O(h)个新节点。

鉴于原始树是一棵完整的树，因此它认为我们创建了O(log n) 个新节点。

于 2018-11-17T15:43:16.440 回答