不成功のバイナリツリー検索

Question

私は、バイナリツリーを使ってn個のキーを含むすべての入力に対する平均検索時間がBig O（lg n）であることを知っていますが、この結果は不満足な研究の結果でしょうか？

Answer 1

厳密に言えば、バイナリツリーがアンバランスな場合は、検索が正常に終了してもO（log n）に達しないことがあります。

バランスのとれたバイナリツリーの場合、残りのツリーのかなりの部分（約半分）を排除することが許可されている一般的な手順のように、結果が失敗しても保持されることは容易にわかります。

Answer 2

はい、バイナリツリー構造では、各チェックでデータセットの半分を本質的に捨てることができます。

あなたが実際に訪れなければならないノードの数を考えて、それがそこにないという決定を下してください。

例：

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

は離れて8とその子供たちを投げ、左に行く、あなたがルートに2.スタートをしたいと言います。 3より小さいので、放置して放置してください。4. 1より大きいので、そこにはありません。

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