O（log n）のバイナリ検索ツリー？

Question

n個のノードを持つバイナリツリーが与えられた場合、O（log n）時間の複雑さで、与えられたツリーがBSTかどうかをチェックできますか？

Answer 1

ノードの量をnとすると、すべての値を少なくとも1回見る必要があるため、ノード数は0であるため、少なくともO（n）が必要です。しかし、nを、サブツリーの合計量のような特別なものにすると、これを達成することができます。 （しかし、これを行うにはちょっとばかげています.1ユーロではなく100セントであれば、より多くのお金を持っているということと同じですから、もっと印象的かもしれませんが、

ここに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; 
} 

とあなたがisBST（木、-infinity、+無限大）で、このメソッドを呼び出します。これは擬似コードであり、もちろんより良い実装が可能です。