-1

次の質問についてサポートが必要です。

サイズ n の並べ替えられた配列が与えられた場合に、配列と同じキーを含む 2-4+ 木を構築するアルゴリズムを説明してください。アルゴリズムは時間 O(n) で実行する必要があります。

並べ替えられた配列から線形時間で赤黒のツリーを構築する方法は既に知っています (挿入後にツリーを修正する関数の償却時間は O(1) であるため)。

ただし、このトリックが 2-4+ ツリーでどのように役立つかわかりません。これらのツリーを挿入した後の償却修正時間と関係がありますか? （そして、それが何かはわかりません...）

それとも私は完全に間違っていますか？

ところで、O(n) で赤黒木から 2-4 木を構築するクラスで見たトリックは使用できません。これは、2-4+ 木アルゴリズムへの単純な配列でなければなりません。

前もって感謝します

4

1 に答える 1

1

赤/黒ツリーと 2-3-4 B ツリーの間には密接な関係があります。実際、この 2 つは互いにアイソメトリーです。つまり、任意の 2-3-4 B ツリーを赤黒ツリーとしてエンコードしたり、その逆を行ったりすることができます。 詳細については、この古い質問で説明しています。

この接続を使用すると、代わりに線形時間で 2-3-4 B ツリーを構築するために、線形時間でリー ブラック ツリーを構築するためのアルゴリズムを適応させることができるはずです。赤黒木を構築し、それを繰り返して構築する B ツリーの構造を決定するか、アルゴリズムを変更して B ツリーを直接構築することができます。

お役に立てれば！

于 2013-02-15T17:24:51.430 に答える