1

次の 2-3-4 ツリーから 15 を削除します。単純に 17 を上に移動することを考えましたが、それが正しいかどうかはわかりません。

次のツリーから 15 を削除します。 ここに画像の説明を入力

削除後の 2-3-4 ツリーはどのようになりますか? この場合、単純に 17 上げるのは正しくないと思います。しかし、よくわかりません。

4

1 に答える 1

1

あなたが持っているツリーは、6 が重複しているため、有効な 2 3 4 ツリーではありません。

2 3 4 ツリーから内部値を削除するには、削除する値を次の最大の項目である 17 である順序で後続する項目に置き換えるだけです。これにより、削除の問題がリーフからの値の削除に軽減されます。ノード。問題は、リーフ ノードの値をどのように削除するかということです。

2 3 4 ツリーの葉から削除する場合、3 または 4 ノードのアイテムを削除するだけです。2 ノードの場合、ノードは空のままになります。これをアンダーフローと呼びます。この問題を解決するには、発生したすべての 2 ノードを 3 ノードまたは 4 ノードに変換する必要があります。隣接する兄弟が 3 ノードか 4 ノードか、またはそれらがすべて 2 ノードであるかによって、処理する必要がある 3 つのケースがあります。これについては、以下のリンクで説明されています。

2 3 4 ツリーからの削除については、スライド 51 から 53 を参照してください。

http://www.serc.iisc.ernet.in/~viren/Courses/2009/SE286/2-3Trees-Mod.ppt

2 3 4 の削除 (および挿入) についても、次の場所で説明および図解されています。

2 3 4 ツリー (C++11) を実装するソース コードについては、以下を参照してください。

http://cplusplus.kurttest.com/notes/tree234.html

于 2014-09-26T16:11:08.860 に答える