二分探索木の検索時間を計算する方法を知っている人はいますか (つまり、最悪の場合、最良の場合、平均的な場合)?
3 に答える
非自己平衡ツリー (検索ツリーでは可能ですが異常) の場合、最悪のケースは 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 の数字の由来です。8
12
14
13
すでに述べたように、縮退した不均衡なツリーは連結リストです。データが順番に到着し、それを不均衡な二分木に挿入した場合、次のようになります。
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
|
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15
その場合に見つけるには、、、、、、、、、、および、したがって O(n)13
を検索する必要があります。1
2
3
4
5
6
7
8
9
10
11
12
13
これを「宿題」としてタグ付けすることをお勧めします。良い出発点は次のとおりです: 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)です。