4

最初に n 個の数のセットが与えられたとします。Search()、Predecessor()、および Deletion() クエリをサポートするデータ構造を構築する必要があります。

検索と先行は、最悪の場合、O(ログ処理 n) 時間かかるはずです。削除には償却 O(log n) 時間かかります。許可される事前時間は O(n) です。最初は O(n) のスペースがあります。しかし、どの段階でも、構造内に m 個の数値がある場合、使用されるスペースは O(m) である必要があります。

この問題は RBT を使用して簡単に解決できますが、配列のみを使用するデータ構造が必要です。配列を使用した RBT の実装は必要ありません。データ構造では、ツリーから着想を得たアルゴリズムを使用しないでください。そのようなデータ構造を考えられる人はいますか?

4

1 に答える 1

0

RBT よりも簡単なある種のツリー構造を提案できます。説明を簡単にするために、その中の要素の数を とします2^k。

最初のレベルは数字だけです。2 番目のレベルには2^(k-1)、バイナリ ツリーのように数字があります。次のレベル a には2^(k-2)数字があり、数字が 1 つになるまで続きます。したがって、ノードを持つ二分木が2^(k+1)あり、親には最大の子の値が含まれます。このツリーを構築するには、時間がO(N)かかります。ツリーはO(n)スペースを消費し、第 1 レベルのコンシューマーn、第 2 n/2、第 3 n/4... などになるため、合計スペースは になりますn + n/2 + n/4 + ... = 2n = O(n)。たとえば、番号 1、2、4、6、8、9、12、14 の次のツリーがあります。

 1  2  4  7  8  9 12  14 

   2    7     9     14 

      7          14

            14

要素を削除するには、バイナリ検索を使用して要素を見つけ、リストで null とマークする必要があります。両方の子 NULL がノードに NULL を設定した場合、ツリーを更新します。k 操作 (木の高さ) または O(log(N)) が必要です。たとえば、12 を削除します。

 1  2  4  7  8  9 NULL(12)  14 

   2    7     9     14 

      7          14

            14

ここで 7 を削除します。

 1  2  4  NUll(7)  8  9 NULL(12)  14 

   2    4            9     14 

      4                 14

            14

ここで、O(log(N)) でまたは前任者を検索する必要があります。二分探索により、最初のレベルで要素またはその前身を見つけます。NULL でない場合は、答えが得られます。NULL がレベルアップする場合、ここに 3 つのバリアントがあります。

  1. ノードに NULL 値があります。上位レベルに移動します
  2. ノードの左の子の値は NULL ではありません。要求された数よりも小さく（ツリー構造のため）、それが答えです。
  3. ノードの値が要求された数よりも大きい場合、上に移動します。
于 2015-11-11T14:41:16.693 に答える