n個のノードを持つバイナリツリーが与えられた場合、O(log n)時間の複雑さで、与えられたツリーがBSTかどうかをチェックできますか?O(log n)のバイナリ検索ツリー?
-1
A
答えて
0
ノードの量を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、+無限大)で、このメソッドを呼び出します。これは擬似コードであり、もちろんより良い実装が可能です。
+0
O(n)アルゴリズムのさまざまなバージョンについては、こちらもご覧ください:http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not / – Lavandysh
関連する問題
- 1. バイナリ検索はO(log n)かO(n log n)ですか?
- 2. バイナリ検索ツリー
- 3. バイナリ検索ツリー
- 4. バイナリ検索ツリー
- 5. O(1)、O(n log n)、O(log n)の複雑さを持つアルゴリズムの例
- 6. log(n!)= O((log(n))^ 2)ですか?
- 7. バイナリ検索ツリーのリスト
- 8. バイナリ検索ツリー式
- 9. バイナリ検索ツリー - ポストオーダーロジック
- 10. バイナリ検索ツリーC++
- 11. deleteバイナリ検索ツリー
- 12. バイナリ検索ツリー?アルゴリズム
- 13. Cバイナリ検索ツリー
- 14. ハッシュテーブルの大きなOとバイナリ検索ツリー
- 15. 床(√2n)のO(log log n)アルゴリズム?
- 16. バイナリ検索ツリーの検索操作
- 17. バイナリ検索ツリーのトラバーサル
- 18. C.のバイナリ検索ツリー
- 19. バイナリ検索ツリーのJavascriptサイズ
- 20. Cのバイナリ検索ツリー、セグメンテーションフォールトエラー
- 21. バイナリ検索ツリーの質問
- 22. バイナリ検索ツリーのセグメンテーションフォールト
- 23. バイナリ検索ツリーのデストラクタ
- 24. バイナリ検索ツリーの再帰
- 25. Cセグメンテーションフォールトのバイナリ検索ツリー
- 26. 空のバイナリ検索ツリーにN個のアイテムを挿入する
- 27. バイナリ検索ツリーtoString Java
- 28. バイナリ検索ツリー削除(C++)
- 29. バイナリ検索ツリー解析
- 30. バイナリ検索ツリーinorderイテレータC++
私はこの質問が[Computer Science](https://cs.stackexchange.com/)に適していると思いますか? – Fildor