9

最悪の場合の操作でもO（n logn）であることを確認するために、 2-3-4木が操作後に高さバランスプロパティ操作をどのように維持するかについての基本的な理解があります。

しかし、なぜ2-3-4しかないのか、よく理解できていません。

なぜ2-3や2-3-4-5などではないのですか？

4

3 に答える 3

17

2-3-4 ツリーの実装には通常、複数のクラス (2NODE、3NODE、4NODE) が必要になるか、アイテムの配列を持つ NODE だけが必要です。複数のクラスの場合、ノード インスタンスの構築と破棄に多くの時間を浪費し、それらの親を変更するのは面倒です。配列を持つ単一のクラスを使用して項目と子を保持する場合、配列のサイズを常に変更することになりますが、これは同様に無駄であるか、未使用の配列要素でメモリの半分以上を浪費することになります。赤黒木に比べてあまり効率的ではありません。

赤黒木には 1 種類のノード構造しかありません。赤黒木には 2-3-4 木との双対性があるため、RB 木は 2-3-4 木とまったく同じアルゴリズムを使用できます (Cormen、Leiserson、および Rivest で説明されている愚かで紛らわしい/複雑な実装は必要ありません。 2-3-4 アルゴリズムよりも複雑ではない AA ツリーに。)

そのため、実装の容易さとメモリ/CPU 効率のための赤黒ツリーです。(AVL ツリーも優れています。よりバランスの取れたツリーを生成し、単純にコーディングするのはばかげていますが、頻繁に作業してわずかにコンパクトなツリーしか維持できないため、効率が低下する傾向があります。)

ああ、そして2-3-4-5-6...などは何も得られないので行われません。2-3-4 は、再帰なしで簡単に実行できるため、2-3 ツリーよりも実質的に有利です (再帰は、特に末尾再帰的にコーディングできない場合は効率が低下する傾向があります)。ただし、B-Tree と Bplus-Tree はほぼ 2-3-4-5-6-7-8-9 などのツリーであり、ノードの最大サイズ n が選択されるため、n レコードを格納できます。単一のディスク セクター。(つまり、各ディスク セクタはツリー内のノードであり、セクタのサイズはノードに格納されているアイテムの数に相当します。)これは、メモリ内で 512 レコードを直線的に検索する時間が、下に移動するよりもはるかに高速であるためです。別のディスク シーク/フェッチを必要とするツリー内のレベル。O(512) はまだ O(1) であるため、ツリーの O(lg n) を維持します。

于 2012-06-12T01:28:32.730 に答える
1

正直、2-3-4本の木は知りませんでした。私のデータ構造クラスでは、2 ～ 3 本の木を教えられました。正直なところ、私たちのほとんどは演習のウェット部分に AVL ツリーを実装していました。

しかし、明らかに、このタイプの木には一般化された (a,b) 木があります。

于 2012-01-06T23:00:19.920 に答える