代码之家 › 专栏 › 技术社区 › Manikanta Nallamalli

O(log n)中的二叉搜索树?

complexity-theory computer-science binary-search-tree tree

-1

Manikanta Nallamalli · 技术社区 · 7 年前

给定一个具有n个节点的二叉树,是否可以在O(log n)时间复杂度下检查给定树是否为BST?

1 回复 | 直到 7 年前

Lavandysh 7 年前

如果n是节点数量,则为否,因为需要至少查看一次所有值,因此至少需要O(n)。但是如果你把n定义为一些特殊的东西,比如子树的总量,你就可以做到这一点。(然而,这样做有点愚蠢,因为这有点像是说如果你有100美分而不是1欧元,你会有更多的钱。这可能看起来更令人印象深刻,但也很奇怪,没有附加值,只是让人困惑,正常人不会这么做)

这是O(n)算法:如果它是BST,那么左树和右树都是BST,其中所有值都将在某个最小值和最大值之间,因此可以创建一个递归方法,该方法有点像这样:

public boolean isBST(subtree, minvalue, maxvalue){
    root=root of subtree;
    if(root>maxvalue || root<minvalue) return false;
    if(has left child)
        if(!isBST(left-child-tree, minvalue, rootvalue)) return false;
    if(has right child)
        if(!isBST(right-child-tree, rootvalue, maxvalue)) return false;
    return true;
}