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

Question

我想弄清楚这个数据结构，但我不明白我们怎么能
告诉我有O（log（n））子树表示查询的答案？
这是一张图片供说明：

谢谢！

Answer 1

如果我们假设上面是一个purely functional binary tree [wiki]，那么当节点是不可变的时，我们就可以复制这个树，这样树中只有值大于x1且小于x2的元素。
让我们从一个非常简单的例子开始来说明这一点假设我们没有任何边界，那么我们可以简单地返回整个树。因此，我们不构造新树，而是返回对树根的引用。因此，我们可以在o（1）中不带任何边界地返回一棵树，前提是该树未被编辑（至少只要使用子树就不会）。
上面的例子当然很简单。我们只是对整个树做一个“拷贝”（不是真正的拷贝，因为数据是不可变的，我们可以返回树）所以让我们致力于解决一个更复杂的问题：我们想要构建一个包含所有大于阈值x1的元素的树。基本上我们可以定义一个递归算法：
None的剪切版本（或表示空引用或空树引用的任何内容）是None；
如果节点的值小于阈值，则返回右子树的“剪切”版本；并且
如果节点的值大于阈值，我们将返回一个inode，该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）的情况下运行，因为对于每种情况（第一种情况除外），我们递归到一个（不是两个）子节点，并且当我们有一个没有子节点（或者至少在我们需要切割子树的方向上没有子树）时结束。
因此，我们不能完全复制这棵树我们重用了旧树中的许多节点。我们只构造了一个新的“曲面”，但大多数“体积”是旧二叉树的一部分。尽管树本身包含o（n）个节点，但我们最多构造o（h）个新节点。我们可以优化上面的内容，这样，如果其中一个子树的剪切版本相同，我们就不会创建新节点但是，在时间复杂度方面，这并不重要：我们最多生成O（H）新节点，并且节点总数小于原始数，或者相同。
在完整树的情况下，树的高度h与O（log n）成比例，因此该算法将在O（logn）中运行。
那么我们如何生成一个元素介于两个阈值之间的树呢？我们可以很容易地将上述内容重写为一个算法 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)

大致来说有两个不同点：
我们将条件从 some_node.value > min更改为 some_node.value < max；并且
如果条件成立的话，我们在 right子child上递归，如果条件不成立的话，我们在左边递归。
现在我们从前面的算法中得出的结论也是可以应用于该算法的结论，因为它只引入了o（h）个新节点，并且节点总数只能减少。
尽管我们可以构造一个同时考虑这两个阈值的算法，但我们可以简单地重用上述算法来构造一个只包含范围内元素的子树：我们首先将树传递给 treelarger函数，然后通过 treesmaller函数得到结果（反之亦然）。
由于在这两种算法中，我们都引入了o（h）个新节点，并且树的高度不能增加，因此我们最多构造了o（2h）个新节点，从而o（h）个新节点。
假设原始树是一个完整的树，那么它就认为我们创建了O（log n）个新节点。