data-structures - 二分探索木の実行時間の複雑さ

Question

特定のキーを持つアイテムを見つけようとする場合、最悪の場合の実行時間はO(n)、nノードの数です。すべてのデータ項目をキーの順に出力しようとすると、最悪の場合の実行時間は になりO(n)ます。特定のデータ項目 (キーがわからない) を検索しようとすると、最悪の場合の実行時間は O(n) になります。ただし、キーとデータが両方とも整数であり、入力項目が挿入される前にランダムにスクランブルされた場合はどうなるでしょうか。実行時間の最悪のケースは同じですか?

Answer 1

最悪の場合、はい。n 個のノードを持つランダムに構築された BST は 2 ^n-1 / n! n が任意の妥当なサイズになるため、縮退的に構築される可能性は非常にまれですが、それでも可能です。その場合、検索は最も深いリーフまで下降する必要があるため、ルックアップに Θ(n) 時間がかかる場合があります。

ただし、予想どおり、ツリーの高さは Θ(log n) になるため、ルックアップには予想される O(log n) の時間がかかります。

ちなみに、ツリーを印刷する時間は、ツリーの形状とは無関係です。常に Θ(n) です。

お役に立てれば！

Answer 2

通常の BST の最悪の場合の実行時間を変更できない場合がありますが、入力をランダム化すると (O(log n) 全体をターゲットにしている場合は、O(log n) 時間未満で)、可能性があります。その最悪のケースが発生することは非常にまれです。ここで数学的分析を参照してください。

保証された O(log n) 時間に関心がある場合は、Red Black Trees などのバランスのとれた BST を使用できます。それを印刷します。