data-structures - 二分探索木のルックアップがO(log(n))なのはなぜですか?

Question

BSTで値を検索するときに、ノードを探している値と比較するたびにツリーの半分を残す方法がわかります。

しかし、なぜ時間計算量がO(log(n)). だから、私の質問は：

N 要素のツリーがある場合、ツリーを調べて特定の値が存在するかどうかを確認する時間の複雑さが O(log(n)) になるのはなぜですか? どうすればそれを取得できますか?

Answer 1

あなたの質問はここでよく答えられているようですが、あなたの特定の質問に関して要約すると、逆に考える方が良いかもしれません。「ノード数が増えると、BST ソリューション時間はどうなりますか」?

基本的に、BST では、ノードの数を 2 倍にするたびに、解決までのステップ数が 1 増えるだけです。これを拡張するために、ノードの 4 倍は 2 つの追加ステップを提供します。ノードの 8 回は、3 つの余分なステップを提供します。ノードが 16 回あると、さらに 4 つのステップが追加されます。等々。

これらのペアの最初の数の基数 2 の対数は、これらのペアの 2 番目の数です。これはバイナリ検索であるため、基数 2 のログです (各ステップで問題空間を半分にします)。

Answer 2

N 要素のツリーがある場合、ツリーを調べて特定の値が存在するかどうかを確認する時間の複雑さが O(log(n)) になるのはなぜですか? どうすればそれを取得できますか?

そうではありません。デフォルトでは、バイナリ サーチ ツリーのルックアップは ではありませんO(log(n))。ここnで、 はノードの数です。最悪の場合、 になってしまうこともありますO(n)。たとえば、次のシーケンスの値をn, n - 1, ..., 1(同じ順序で) 挿入すると、ツリーは次のように表されます。

                  n
                 /
              n - 1
               /
            n - 2
             /
           ...
           1

1値を持つノードのルックアップには、O(n)時間の複雑さが伴います。

ルックアップをより効率的にするには、最大の高さが に比例するようにツリーのバランスlog(n)を取る必要があります。このような場合、ルックアップの時間の複雑さはO(log(n))、葉を見つけることが操作によって制限されるlog(n)ためです。

しかし、繰り返しますが、すべての二分探索木が平衡二分探索木であるとは限りません。O(log(n))時間の複雑さを保証するには、バランスを取る必要があります。