计算 O(LogN) 中二叉搜索树范围内的节点数

Question

给定一个 BST 和两个整数 'a' 和 'b' (a < b)，我们如何在 O(log n)?

我知道在LogN时间内很容易找到a和b的位置，但是不遍历复杂度O(n)怎么计算中间的节点数呢？

Answer 1

想法很简单。

从根开始遍历BST
检查每个节点是否在范围内。如果它在范围内，则计数++。并重现其双children。
如果当前节点小于范围的低值，则向右递归child，否则向左递归child。

时间复杂度为O(height + number of nodes in range)..

关于为什么不是 O(n) 的问题。

因为我们不是遍历整棵树也就是树中的节点数。我们只是根据parent的数据遍历所需的子树。

伪代码

int findCountInRange(Node root, int a, int b){

    if(root==null)
       return 0;
    if(root->data <= a && root->data >= b)
         return 1 + findCountInRange(root->left, a, b)+findCountInRange(root->right, a, b); 
    else if(root->data < low)
         return findCountInRange(root->right, a, b);
    else 
         return findCountInRange(root->left, a, b);

}

Answer 2

将BST的中序遍历存储在数组中（会排序）。搜索 'a' 和 'b' 将花费 log(n) 时间并获取它们的索引并取差。这将给出 'a' 到 'b' 范围内的节点数。

space 复杂度 O(n)

Answer 3

在二叉搜索树的每个节点中，还要计算树中小于其值的值的数量（或者，对于下面脚注中提到的不同树设计，其左侧的节点子树）。

现在，首先找到包含值 a 的节点。获取已存储在此节点中的小于 a 的值的计数。这一步是 Log(n).

现在找到包含值 b 的节点。获取存储在此节点中的小于 b 的值的计数。这一步也是Log(n).

将这两个计数相减，得到 a 和 b 之间的节点数。此搜索的总复杂度为 2*Log(n) = O(Log(n)).

_{参见 this video。教授在这里用Splay Trees解释了你的问题。}

Answer 4

简单的解决方案：

从根节点开始检查
如果节点落在范围内，则将其加1并递归检查左右child

如果节点不在范围内，则检查范围内的值。如果范围值小于根，那么绝对可能的场景是左子树。否则检查右子树

这是示例代码。希望它清除。

if (node == null) {
    return 0;
} else if (node.data == x && node.data == y) {
    return 1;
} else if (node.data >= x && node.data <= y) {
    return 1 + nodesWithInRange(node.left, x, y) + nodesWithInRange(node.right, x, y);
} else if (node.data > x && node.data > y) {
    return nodesWithInRange(node.left, x, y);
} else {
    return nodesWithInRange(node.right, x, y);
}

时间复杂度：- O(logn)+ O(K)

K是x和y之间的元素个数。

它不是很理想，但在您不想修改二叉树节点定义的情况下很好。

计算 O(LogN) 中二叉搜索树范围内的节点数

Count number of nodes within range inside Binary Search Tree in O(LogN)

algorithm

binary-tree

data-structures