0

私は解決する必要があるこの問題を抱えています。私は答えを探しているのではなく、どこへ行くべきかについてのヒントを探しています。アルゴリズムはありますが、O(log n) ではありません。

二分木 T と、T のノード数以下の正の整数 k が与えられた場合、T の要素 v を特定する疑似コードを記述して、T の正確に k − 1 個の要素が v よりも小さくなるようにします。コードには時間がかかるはずです。 T の高さに最も比例します。

ここでの基本的な考え方は、最初に左側のツリーをチェックし、左側のツリーのサイズをチェックするというものです。左の木のサイズが k-1 より大きい場合は、左の検索を続けます。それ以外の場合は、右を検索します。左側のツリー全体に k-1 個の要素を持つノードが含まれていない場合は、右側のサブツリーを検索します。問題は、最悪の場合、ツリー内のすべてのノードを検索する必要があるため、これが O(log n) ではないことを知っていることです。

足りないものはありますか？ヒントやヘルプは素晴らしいものですが、答えだけを教えてはいけません。

4

3 に答える 3

0

（私は、ツリーが実際には二分探索木であり、単なる古い二分木ではないと仮定しています）

アルゴリズムはO(d)で、dはツリーの最大深さです。

これは、その比較を行うたびに、1 つ下のレベルに進むためです (まだ要素が見つからないと仮定します)。したがって、ツリー内のレベルと同じ数の比較を行うことになります。

したがって、ツリーが本当にバランスを崩していない限り、実際にすべての要素を調べることはありません。実際、ツリーのバランスが取れていると想定できる場合は、すでに問題ありません (なぜですか?)。

于 2013-09-28T01:22:33.563 に答える
0

通常の二分木について話している場合、そのようなノードを見つけるにはツリー全体を探索する必要があることを証明するのはかなり簡単なので、二分探索木について話していると仮定します。

二分探索木では、ノード N より小さいものは次のとおりです。

  • ノード A、その左の子、およびそのすべての子孫。ここで、ノード B はノード A の右の子であり、ノード B はノード N またはその祖先のいずれかです。

        A
   / \
  X   B
 /     \
Y      ...
 \     /
  Z   N

    A、X、Y、Z はすべて N より小さい (同じ規則により、B も N より小さい)。

  • ノード N の左の子

すべての子供が小さいだけだと思っていたのではないかと思います。

**スポイラー警告**

アルゴリズム：

m要素が小さいノードを探しています...

  1. 上から始めます。

  2. Let x= 左サブツリーのノード数 (左の子がない場合は x = 0)

  3. の場合x = m、現在のノードを返します。

  4. の場合x < m、左に再帰します。

  5. の場合x > m、設定m = m - x - 1して右に再帰します。

左または右にしか移動せず、ノード数は (ノード レベルで指定されているため) 一定であるため、実行時間は、バランスの取れたツリーO(h)にhあるツリーの高さですO(log n)。

于 2013-09-28T11:07:07.350 に答える
0

これは、quickselect とほぼ同じアルゴリズムです。左の分岐のサイズに応じて、左または右の分岐に再帰します。

Find(T, k) :=
    size(T.left) == k - 1 -> return T
    size(T.left) > k - 1 -> return Find(T.left, k)
    size(T.left) < k - 1 -> return Find(T.right, k - size(T.left) - 1)

size(T) が O(1) であることは、質問で直接指定されていません (ただし、コメントで明確にされています)。

高さは各再帰ステップで少なくとも 1 ずつ減少するため、これには最大で height(T) ステップかかります。

これを繰り返し書くこともできます：

Find(T, k) := 
   while size(T.left) != k - 1:
       if size(T.left) > k - 1:
           T = T.left
       else:
           T = T.right
           k -= size(T.left) + 1
   return T
于 2013-09-28T12:21:57.163 に答える