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

私が間違っていなければ、a の破壊に関しては、2-3-4 tree4 つの子を持つ (再帰的に) 二分木に似ているはずです。以下に、単純な再帰的削除を含むデストラクタ固有のコードを示します。

問題は、まだリークが発生することです。ファイルには、私の 2-3-4 ツリーのみが含まれています。

これは s のデストラクタを実装する正しい方法2-3-4 treeだと思いますが、私の実装は正しくないようです。誰かが私の論理の間違いを指摘できますか? 私は図を作成しましたが、それは健全なようです。

私のノード設計:

私の挿入コード。現時点では削除機能を実装していません。

---

ヴァルグラインド:

2-3-4 ツリーの高さは、ノードの挿入順序によって異なる場合があることがわかりました。

たとえば、1,2,3,4,5,6,7,8,9,10 は高さ 2 のツリーを生成します

この順序で挿入している間：

たとえば、1, 5, 10, 2, 3, 8, 9, 4, 7, 8 は高さ 1 のツリーを生成します

これは 2-3-4 ツリーの通常の特性ですか? その場合、ノードを順番に挿入すると、非常に不均衡なツリーが生成されます。2-3-4本の木はバランスの取れた木であるべきだと思いましたか?

ありがとう。

現在、2-3-4 ツリーを使用するプログラムを作成しようとしていますが、挿入機能に問題があります。ここに関連するコードがあります..

常に 19 行目で中断し、メモリ アドレス エラーが発生します。私はそれをデバッグしようとしましたが、文字列ファイル内の 2245 行で壊れています (それがまったく役立つ場合)。その情報はあまり役に立たなかったので、誰かがここで何が間違っているのか正確に教えてくれるでしょうか?

私は自分のデータ構造クラスの資料を見直していましたが、これら 3 種類のツリーの使用法にちょっと混乱しています。では、二分探索木、2-3 木、B 木をそれぞれより適切に使用する必要がある状況は何ですか? 長所と短所は何ですか？

どうもありがとう！私はデータ構造にまったく慣れていません...

私は2-3-4ツリーを持っていますが、葉だけが値を持つように変更されています。葉が正確な言葉かどうかはわかりません。葉 (私の説明では) は、ツリーの下部にある最大の深さのノードです (これらはツリーの最後にあるノードです)。各休暇には 1 つの値があります。他のノード (リーフではない) には、子ノードの最小値の「値」があります。したがって、これは有効なツリーです:

最大の複雑さ O(log n) を持つ疑似コードをいくつか書く必要があります。最小値 (ツリーから最小値を返す)、insert(k) (k 値で新しい休暇を挿入)、キー (x,k) の減少 (リスト x のキーを k に変更)、削除 (x) ツリーから休暇を削除する必要があります。 min を抽出します (最小値の leave を削除します)。

私は自分で何かを書こうとしましたが、これが正しいかどうか、複雑な条件を満たしているかどうかはわかりません。

最低限の機能は大丈夫だといいのですが、挿入機能は大丈夫ですか？複雑すぎませんか？複雑な条件を満たすのを手伝ってくれませんか？他の機能で私を助けてくれませんか（言葉のアルゴリズムで十分です:)）。

2-3-4 ツリーで挿入の順序がどのように重要であるかを知っている人はいますか? それともBツリー？

最小の高さの式は log _m (k+1) のようで、m は最大数です。子の数で、k はキーの数です

最大高さの式は次のとおりです。log _n ((k+1)/2) ここで、n は最小数です。内部ノードが持つことができる子の数。

しかし、実際にこれらの結果が得られるのは、どの挿入シーケンスですか?! 知らない。

2-3-4 ツリーの高さを最小限に抑えることが提案されています。たとえば、線形シーケンスの中央値を取得します。1,2,3,4,5,6,7,8 が 4 であり、それを挿入して、すすぎの前に、中央値の両側のサブリストについて繰り返します。これは本当ですか？もしそうなら、どのシーケンスが高さを最大化しますか?

2-3-4 ツリーで明確化していただければ幸いです...次のように定義されたツリーがあるとします。

私の質問は、実際には、ノードの変数 (firstData、secondData、 thirdData) にすでに何らかの値がある場合に、ノードがいっぱいである (3 つの値がすべて含まれている) かどうかをどのように知ることができるかということです。

例:
ルート: |4| ルートの左の子:|1,2|
ルート |7,9| の右の子

ここで root には 1 つの値 (4) があります。私の質問は、彼の他のすべての変数 (secondData、 thirdData) には何らかの値があるため (たとえそれがゴミであっても)、実際に 1 つの値を持っていることをどのように知ることができるかということです.. よろしくお願いします!