binary-tree - 二分木探索の失敗

Question

検索が成功した場合、二分木を使用した n 個のキーを含むすべての入力に対する平均検索時間は Big O (lg n) であることがわかっていますが、この結果は失敗した研究にも当てはまりますか?

Answer 1

はい、バイナリ ツリー構造により、各チェックでデータ セットの半分を本質的に破棄できます。

そこにないと判断するには、実際にいくつのノードにアクセスする必要があるかを考えてみてください。

例：

     5
     /\
    3  8
   /\  /\
  1 4  6 9

2. ルートから始めて左に進み、8 とその子を捨てます。3 より小さいので左に 4 を捨てます。1 より大きいのでありません。

この場合、5、3、1 だけを訪れました。これは、新しいノードを挿入するのと同じと考えることができます。