問題タブ [2-3-4-tree]

私は現在データ構造コースに参加しており、2-3-4木とスプレー木について学びました。どのような状況で、スプレーツリーの代わりに2-3-4ツリーを使用するのでしょうか。それらは両方とも自己バランス型であり、ソートされているので、それらの間にそれほど大きな違いは見られません。

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

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

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

赤黒の木と 2-3-4 の木の両方と、それらが高さのバランスを維持して最悪の場合の操作が O(n logn) であることを確認する方法について、基本的な理解があります。

しかし、ウィキペディアからこのテキストを理解することはできません

2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。

操作がどのように同等かわかりません。ウィキペディアのこの引用は正確ですか? 操作が同等であることをどのように確認できますか?

このコードでは、numitems を静的変数として宣言し、クラスの outsize を初期化しました。でのエラーの主な原因だと思っていました(return (numitems==order-1));が、ここにも関連する問題があるため(childarrray[0]==NULL)、完全にこのコードは Java から取得して C++ に変換したものであるため、参照の代わりにポインターを追加しました。私のコードのエラーを修正するのを手伝ってください。

私は、Sedgewick によって記述された 2 つのモード、Bottom-Up 2-3 または Top-Down 2-3-4 のいずれかで動作できる LLRB パッケージを実装しています(コード- 改善されたコードですが、2-ここに3 つのツリーがあります。RS のポインターに感謝します)。

Sedgewick は、2-3-4 モードについて多くの時間を費やしていますが、2-3 モードのツリー操作について非常に明確に説明しています。彼はまた、挿入中の色反転の順序を単純に変更するだけで、ツリーの動作がどのように変化するかを示しています (2-3-4 の場合は下方向に分割するか、2-3 の場合は上方向に分割します)。

ただし、彼は次のように 2-3-4 LLRB での削除についてごまかしています。

次のページのコードは、LLRB 2 ～ 3 ツリーの delete() の完全な実装です。これは、トップダウンの 2-3-4 ツリーへの挿入に使用されるアプローチの逆に基づいています。検索パスの途中で回転とカラー フリップを実行して、検索が 2 ノードで終わらないようにします。一番下のノードを削除できるようにします。メソッド fixUp() を使用して、insert() コードの再帰呼び出しに続くカラー フリップと回転のコードを共有します。fixUp() を使用すると、検索パスに沿って右寄りの赤いリンクとバランスの取れていない 4 つのノードを残すことができ、これらの条件がツリーの途中で修正されることが保証されます。(このアプローチは 2-3-4 ツリーでも効果的ですが、検索パスから外れた右側のノードが 4 ノードの場合は余分な回転が必要です。 )

彼の delete() 関数:

私の実装では、2 ～ 3 ツリーのすべてのツリー操作に対して LLRB 2 ～ 3 の不変条件が正​​しく維持されますが、2 ～ 3 ～ 4 ツリーの右側削除のサブクラスでは失敗します (これらの削除の失敗により、右寄りの赤いノードが発生しますが、雪だるま式にツリーの不均衡と最後に null ポインターの逆参照)。LLRB ツリーを説明し、いずれかのモードでツリーを構築するためのオプションを含むコード例の調査から、2-3-4 LLRB からの削除を正しく実装していないようです (つまり、Sedgewick の java上とここ）。

「検索パスから離れた右側のノードが 4 ノードの場合に余分なローテーションを行う」という彼の意味を正確に理解するのに苦労しています。おそらくこれは左回転ですが、いつ、どこで？

fixUp() を呼び出す前、または fixUp 関数の最後に、4 ノードの同等物 (すなわち RR ノード) または右寄りの 3 ノード同等物 (BR ノード) を通過して左に回転すると、同じ不変の矛盾が発生します。 .

これは、私が見つけた最小の失敗例のツリー状態です (0 からそれぞれの最大値までの要素を順次挿入することによって生成されます)。

ツリーの最初のペアは、要素 15 の削除前の不変適合状態から、削除後の明らかに壊れた状態への遷移を示しています。

2 番目は基本的に上記と同じですが、0..16 のうち 16 が削除されています (15 を削除すると同じトポロジになります)。不変矛盾がルートノードを越えることに注意してください。

重要なのは、ツリーを下ってターゲット ノードに移動する際に生成された違反を元に戻す方法を理解することです。次の 2 つのツリーは、上の最初のツリーがそれぞれ左右に移動した後 (削除せず、fixUp() で元に戻す前) にどのように見えるかを示しています。

fixUp なしで「-1」を削除しようとした後:

fixUp なしで '16' を削除しようとした後:

ノードに赤い右の子しかない場合にウォークを左に回転しようとすることは解決策の一部であるように見えますが、2 つの赤い右の子が連続して正しく処理されず、両方の子が赤の場合に FlipColor を前に付けます。状況はさらに改善されるように見えますが、依然としていくつかの不変条件に違反したままです。

右の子の右の子が赤で、兄弟が黒かどうかをさらに確認し、これが真の場合は左に回転すると、1 回だけ失敗しますが、この時点では、新しいエピサイクルではなく、新しい理論が必要なように感じます.

何か案は？

参考までに、私の実装はこちらから入手できます(いいえ、Java ではありません)。

ファローアップ：

私がこれに興味を持った理由の 1 つは、2-3-4 LLRB ツリーよりも 2-3 LLRB ツリーの方が効率的であるという多くの主張を確認するためでした。私のベンチマークでは、挿入と削除でこれが確認されています (2 ～ 3 の方が約 9% 高速です)。

次の時間は代表的なものであり、実行全体で一貫しています。

1 列目はベンチ名、2 列目は操作数、3 列目は結果です。i5M 2.27 のベンチマーク。

2 ～ 3 本の木と 2 ～ 3 ～ 4 本の木の枝の長さを見てきましたが、検索の違いを説明するものはほとんどありません (ルートからノードまでの平均距離と、それぞれ 10000 個のランダムな挿入を持つ 1000 本の木の SD):

私の本によると、AVL ツリーで偶数の高さのノードから奇数の高さのノードに移動する赤いリンクに色を付けると、(完全にバランスのとれた) 2-3-4 ツリーが得られます。ここで、赤いリンクは必ずしも左寄りではありません。しかし、正確にはわかりません。いくつかの例で試してみると、行き詰まります。誰かが私のためにそれを説明してもらえますか?

以下に示す2-3-4ツリー（JavaのData Structures＆Algorithm、第2版から）では、挿入すると、正しい子（子、分割を行わずに）の直後にスポットしますか？9983/92/10499C97

ノード クラスでノード配列を初期化しようとしています。これらはプライベート メンバーです。

残念ながら、コンパイルされません。エラーは次のとおりです。

次のJavaコードから。

コードを簡単に変換するのを手伝ってください。注文をパブリックとして宣言する必要がありますか? const int node::order=4 のように、クラス外で順序の宣言も試みましたが、まだ成功していません。何が問題なのですか? メンバーを保持する配列が必要です。サイズは順序または 4 である必要があります。本を読んでいるときに、この本から C++ で Java コードを書いているときに必要なものを著者が言っていました。ポインターと書かれているので、ポインターを追加しましたが、まだ成功していません。

これは、上記のsqlに示すコードを入力してテーブルを作成したときの、元のphpmyadminエラーメッセージです。

このコードを正しく書く方法と何が悪いのかを理解したいと思います。