18

二分探索木の検索時間を計算する方法を知っている人はいますか (つまり、最悪の場合、最良の場合、平均的な場合)?

4

3 に答える 3

34

非自己平衡ツリー (検索ツリーでは可能ですが異常) の場合、最悪のケースは O(n) であり、これは縮退したバイナリ ツリー (連結リスト) の場合です。

この場合、目的の要素を見つける前に、平均してリストの半分を検索する必要があります。

最適なケースは、完全にバランスの取れたツリーの O(log 2 n) です。これは、ツリー レベルごとに検索スペースを半分に削減するためです。

平均的なケースはこれら2つの間のどこかにあり、データに完全に依存します:-)

データがツリーに挿入される順序を制御できることはめったにないため、挿入または削除のたびに少し時間が追加されますが、検索が大幅に高速化されるため、通常は自己均衡ツリーが適しています。それらの最悪のケースは、バランスの取れていない木よりもはるかに優れています.

                 8
         _______/ \_______
        /                 \
       4                  12
    __/ \__             __/ \__
   /       \           /       \
  2         6        10        14
 / \       / \       / \       / \
1   3     5   7     9  11    13  15

この完全にバランスの取れたツリーでは、すべてのレベルで 2 n -1 ノードが得られることがわかりnます。つまり、15 個のノードの場合、それを見つけるために 4 個以上のノードを検索する必要はありません (たとえば、 を検索するには、 、、および13を検索します)。これが log 2 n の数字の由来です。8121413

すでに述べたように、縮退した不均衡なツリーは連結リストです。データが順番に到着し、それを不均衡な二分木に挿入した場合、次のようになります。

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
                                           |
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15

その場合に見つけるには、、、、、、、、、、および、したがって O(n)13を検索する必要があります。12345678910111213

于 2009-02-09T00:03:29.893 に答える
12

これを「宿題」としてタグ付けすることをお勧めします。良い出発点は次のとおりです: http://en.wikipedia.org/wiki/Binary_search_tree

一般に、バランスの取れた二分探索木には、O(log n) の最悪の場合のルックアップ、O(1) の最良の場合 (目的の値がルートである場合)、および O(log n) の平均的な場合 (葉) があります。親よりも指数関数的に多くの値が含まれています)。

最悪のケースは最も興味深いものであり、バイナリ ツリーの最初のレベルには 1 つのノードがあり、2 番目のレベルには 2 つのノードがあり、3 番目のレベルには 4 つのノードがあるなどを認識することで簡単にわかります。したがって、深さnの二分木のノード数は正確に2^n - 1です。指数関数の数学的逆数は対数、つまりO(log n)です。

不均衡なツリーは、リンクされたリストと同じくらい悪い場合があり、次のような形状になる場合があります。

  1
 / \
    2
   / \
      3
     / \
        4
       / \

この状況では、最悪のアクセス時間はO(n)です。

于 2009-02-09T00:04:56.897 に答える