バイナリツリーとバイナリ検索ツリーBig oh Analysis

Question

バランスのとれたバイナリ検索ツリーは、バランスのとれたバイナリツリーよりも速く大きな時間で次のタスクを完了するのに役立ちますか？

いくつかの値vよりも小さいツリー内のすべての要素のリストを作成する。ノーBST内のすべての値をvよりも小さい場合にはどのようなので、私の意見では

。そして、あなたが各訪問しなければなりませんそれはO（n）であり、これはバイナリツリーより優れていません。

正しいですか？私の意見で

Answer 1

何BST内のすべての値をvより 小さい場合。そして、あなたは、各ノードを訪問しなければならない、それがバイナリよりも良くないですO（n）の どうなるか理由はありません木。

正しいですか？

です。しかし、すべての実用的な目的のためには、 "平らな"バイナリツリーで常にがvより小さいものを見つけるためにすべてのノードを訪ねなければならないので、BSTでは順序通りのトラバーサルvより小さい。