2-3ツリー-C++のデータ構造とアルゴリズム

2-3ツリーは、ツリーのすべてのノードが2ノードのいずれかであるデータ構造内のツリーの一種です

または3ノード。これは特別なタイプのBツリーです。 注文3で。

ツリー内の2ノードは、1つのデータ部分と2つの子ノードを持つノードです。

ツリー内の3ノードは、2つのデータ部分と3つの子ノードを持つノードです。

図：-2-3木

2-3ツリーのプロパティ：-

• すべての内部ノードは、2ノードまたは3ノードのいずれかです。

• 1つのデータ部分を含むノードは、正確に2つの子を持つ2ノード、または子を持たないリーフノードにすることができます。

• 2つのデータ部分を含むノードは、正確に3つの子を持つ3つのノードのみになります。

• すべてのリーフノードは常に同じレベルにあります。

• 2-3木は、常に高さのバランスが取れた木です。

• 検索操作は2〜3ツリーで高速かつ効率的です。

2ノード：-

• ちょうど2人の子供。

• 体重の少ない左の子供。

• 体重の多い右の子供。

• 子のないリーフノードにすることができます。

3ノード：-

• 正確に3人の子供。

• 2つのデータ値。

• 左のデータ値よりも体重が小さい左の子。

• 両方のデータ値の間に重みがある中間の子。

• 体重が適切なデータ値よりも大きい適切な子。

• リーフノードになることはできません。

2-3ツリーでの操作：-

1。 2-3ツリーで検索する

• データが並べ替えられる二分探索木の検索操作に似ています。

• 2-3ツリーでXを検索します。

• ツリーが空の場合→Falseを返す

• ルートノードに到達したら、False（見つかりません）を返します

• Xが左側のデータ部分よりも小さい場合は、左側のサブツリーを検索します

• Xが左のデータよりも大きく、右のデータよりも大きい場合は、中央のサブツリーを検索します。

• Xが右側のデータ部分よりも大きい場合は、右側のサブツリーを検索します。

2。 2-3ツリーへのノードの挿入

• Xを2-3ツリーに挿入します。

• ツリーが空の場合→ルートとしてXを追加します。

• Xの正しい位置を検索し、リーフノードとして追加します。

• データ部分が1つあるリーフノードがある場合は、Xを追加すると、リーフノードは2-ノードになります。

• リーフノードに2つのデータ部分がある場合は、Xを追加します。一時的な3ノードを分割し、並べ替え順序に従ってデータを親ノードに移動します。

2-3ツリーを作成し、ノードを順番に追加します→10、5、8、15、23、21

3。 2-3ツリーのノードの削除

• 2-3ツリーのXを削除します。

• ツリーが空の場合はfalseを返します。

• Xの位置を検索して削除し、ツリーを調整します。

• Xが3ノードの一部である場合は、Xを削除し、左の値と中央の値を調整します。また、必要に応じて、ノードの祖先の左と中央の値を調整します。

• Xが2ノードの一部である場合は、ツリーを再帰的に調整して分割し、ノードを並べ替えた順序で配置します。