私はこの単純なツリーの名前を探しています。これは、バイナリ検索ツリーのかなり簡単な一般化です。このツリーの名前は何ですか?
これは説明です。ツリーの各ノードは固定数の最大鍵MIと最小数の鍵(ちょうど1)を有する。鍵は順序付けされる。すべてのノードには、子ノードへのMI + 1外部リンクがあります。多少なりともbツリーに似ています。子ノードには、親の2つの近接キーの間隔内にあるキーのみが含まれます(bツリーのように)。
挿入と削除の仕組みは異なります。
挿入:
ルートから始めます。
私がチェックしているノードにスペースがある場合は、MIキーがないので、フルではないので、正しい位置にキーを追加します。
ノードがいっぱいの場合は、そのノードをチェックインします。この範囲の子がない場合は、キーのみで作成します。その他
の削除:削除で
、私はノード内のインスタンスのための「ACE」を持っていた、と私は、「E」を削除する必要がありますが、「C」および「E」の間の間隔に子供があれば私は子供の最大の要素を得て、それを "E"に置き換えます(要素を削除すると子要素から親要素に別の要素を移動する必要があるため、ここで再帰する必要があります)。これより少し複雑ですが、一般的に、要素を子から削除されたキーを所有するノードに移動することがあります。
私はこれが非常に非公式に指定されていることを理解していますが、私はバイナリツリーの些細な一般化のように見えるものの名前を見つけることができませんでした。
ノードにはMIキーがありますが、挿入時には「子」と言います。子供がその重要な情報としてどのように選ばれたかを明確にしてください。 – marcog
@margoc:私は、現在のノードがいっぱいであれば、既に持っている2つのキーで区切られた範囲にリンクされている子に行きます。だからMIが4の場合、ルートノード「A C M Z」に「E」を追加すると、A-C範囲にリンクされた子に移動しようとします。何もない場合、私はそれを作成します。 – antirez