1

seek（u、v）関数を定義する必要があります。ここで、uはツリー内の新しいノード（検索を開始するノード）であり、vは新しいノードの下の子孫の数であり、この関数はインデックスを返します。最高のキー値の。ツリーにはBSTがなく、多くの子を持つノードが存在する可能性があります。例：

input:
5             // tree with 5 nodes
1 3 5 2 7     // the nodes' keys
1 2           // 1 and 2 are linked
2 3           // 2 and 3 are linked
1 4           // 1 and 4 are linked
3 5           // 3 and 5 are linked
4             // # of seek() requests
2 3           // index 2 of tree, which would be key 5, 3 descendants from index 3 
4 1           // index 4 of tree, but only return highest from index 4 to 4 (it would 
              // return itself)
3 2           // index 3, next 2 descendants
3 2           // same

output:
5             // Returned index 5 because the 7 is the highest key from array[3 'til 5]
4             // Returned index 4 because the range is one, plus 4's children are null
5             // Returned index 5 because the 7 is the highest key from array[4 'til 5]
5             // Same as prior line

新しいルートを新しい赤黒木に入れることを考えていましたが、各ノードの後続または先行情報を効率的に保存する方法が見つかりません。配列に入れることも考えていますが、不均衡でソートされていないツリーの性質上、ツリーがソートされることを保証するものではありません。さらに、BSTではないため、順序どおりのツリーウォークを実行できません。特定の範囲から最高のキーを取得する方法について何か提案はありますか？

4

1 に答える 1

1

「新しいノードの下の子孫の数」の意味がよくわかりません。あなたがそれを言う方法では、それはある種の課されたツリーウォーク、または少なくともあなたがノードを訪問しなければならない順序があることを意味します。その場合、あなたが何を意味するのかをより完全に説明するのが最善でしょう。

答えの残りの部分では、あなたがuからの距離を意味すると仮定します。

純粋なアルゴリズムの観点からは、ツリーについて何も想定できないため、結果を取得するには、グラフの関連するすべての頂点（つまり、uから<= vの距離にある頂点）にアクセスする必要があります。これは、ノードを訪問する順序は重要ではないため、部分的なツリートラバーサル（深さ優先や幅優先など）で十分かつ必要であることを意味します（uの下の関連するすべてのノードにアクセスする必要があるため）。

可能であれば、次のように定義されたカップル（インデックス、キー）を返す再帰関数seek'（u、v）を使用する方が簡単です。

  • v> 1の場合、seek'（u、v）を、uのwの息子のカップル（u、key（u））とseek（w、v-1）の中で2番目のコンポーネントを最大化するカップルとして定義します。
  • else（v = 1）seek'（u、v）を（u、key（u））として定義します

次に、seek（u、v）= first（seek'（u、v））があります。

私が言ったことはすべて、入力からツリーを構築したこと、またはノードとその子のキーをそのインデックスから簡単に取得できることを前提としています。

于 2012-10-26T15:25:13.923 に答える