前ページ・前々ページで 赤黒木・AVL木 を紹介してきましたが、 そうなると次はやはり B木 の出番でしょう。 しかし、いきなりバリバリの多分木であるB木に挑戦するのはちょっとハードルが高いかもしれません。 そこで、B木の一番簡単なケースである2-3木で肩ならしをしましょう。 もし、このページの内容が難しいと感じるようなら、 まず、赤黒木 や AVL木 のページを読んでみてください。
2-3木は平衡探索木の一種です。 平衡探索木では、要素の検索・挿入・削除などの操作が、 いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に \(O(n)\) の計算量が必要になる場合があります。
それでは、2-3木に関して説明しましょう。2-3木とは２分探索木の親戚です。 具体的に示すと図1.のようになります。 図1.で 4 や 6,8 などが入っている箱をノードと言います。 ２分探索木のノードが１つか２つの枝を持っているのに対して、 2-3木では２つか３つの枝を持ちます。 そして、枝と枝の間には要素が１つあります。 つまり、１つのノードに要素が２つ割り当てられることがあるわけです。
|
|
図1.で 6,8 を要素に持つノードに注目してください。 6 より小さい 5 は左に枝に、6 と 8 の間の 7 は真ん中の枝に、 8 より大きい 9,10 は右の枝に配置されています。 ２分探索木の簡単な拡張になっていることが分かると思います。
ここで、根(root)とは 4 が割り当てられている最上位のノードのことです。
また、葉とは空のノード(Empty)のことです。
1 や 9,10 が割り当てられているノードの下には本来枝があるのですが、
簡略化のため図示はしていません。
空のノードはこれらの枝の先にあると考えます。
各枝の先にある木構造のことを部分木と言います。
最大の部分木は2-3木自身です。
そして忘れてはならない重要な性質があります。それは、 全ての葉から根までのパス上のノード数は等しい ということです。 赤黒木やAVL木では木のバランスは完全には取れていませんでしたが、 2-3木では完全にバランスしていることになります。
2-3木とは以下の条件を満たす平衡探索木です。
図1.を例に、要素 7 を検索する方法を説明しましょう。 検索はまず、根から開始されます。図1.では 4 のノードです。 7 は 4 より大きいので、4 の右の部分木に含まれているはずです。 そこで、右の部分木を調べます。右の部分木の根には 6,8 が含まれています。 7 は 6 よりも大きく 8 より小さいので、 6 と 8 の間の部分木に含まれているはずです。 そこで、6 と 8 の間の部分木を調べると 7 が見つかります。 もちろん、葉までたどり着いて目標の要素が見つからない場合もあります。 その場合は、2-3木に目標の要素は含まれていないことが分かります。
では、2-3木の挿入操作について説明します。 赤黒木やAVL木同様まず要素が既に登録されているかどうか検索します。 既にあればそのノードを置き換え、無ければ挿入することになります。 すなわち、挿入は常に最下層のノードで開始されます。
挿入にはアクティブなノードを挿入します。アクティブなノードとは、
他のノードに触れると反応して木の形を変えるノードのことです。
挿入時のアクティブなノードは挿入する要素を１つ持ち、
部分木(枝)を２つ持ちます。部分木は最初は空(Empty)です。
まず、親ノードが２分岐の場合の挿入操作のパターンを図2.に示します。 通常のノードを四角で、アクティブなノードを丸で表しています。 p が挿入される要素です。三角は部分木を表しています。 アクティブなノードが親ノードと反応して３分岐のノードになり安定します。
|
次に、親ノードが３分岐の場合の挿入操作のパターンを図3.に示します。 親ノードが分割され２分岐のノードが新たに３つ生成されます。 １つはアクティブなノードで、残りの分割されたノードを子に持ちます。
|
|
|
新たにアクティブなノードが生成されるので、 さらに上位のノードに対して挿入操作を再帰的に繰り返すことになります。 そして根までアクティブなノードが到達した場合は、 アクティブなノードを通常のノードに変換して新たな根にします。 説明が前後しますが、空の2-3木にノード挿入する場合も、 アクティブなノードを通常のノードに変換し根にします。
ここで、具体的な挿入の例を示しておきましょう。以下のようになります。
左端において、赤で示したアクティブなノード 1 が挿入される例です。
ここでは、三角は Empty だと思ってください。
もちろん、部分木とみなすことも出来ます。
アクティブなノードの親ノード 2,3 は３分岐なので、
アクティブなノードに触れると分割され、
新たにアクティブなノード 2 が生成されます。
ノード 2 は親ノード 4 に挿入されることになります。
ノード 4 は２分岐なので、アクティブなノードを取り込んで安定します。
もう１つ、アクティブなノードが根に到達した場合の例をあげておきます。 アクティブなノードが根に到達した場合、 アクティブなノードをそのまま通常のノードに変換して新たな根にします。 このとき、木の高さが１段増えることになります。
気がついた人もいると思いますが、 2-3木の挿入では赤黒木やAVL木のような回転の操作がありません。 回転は部分木の高さを変えてしまうので木のバランスが変化します。 2-3木はバランスの状態を全く変えないので、 最初の木がバランスしていれば最後まで完全にバランスが取れています。 そして最初の木は空ですから、バランスは取れていると見なせます。 そのため2-3木は完全にバランスしているのです。
ここでは、Haskell で2-3木を使った ツリーソート を実装します。 もちろん、2-3木を使ったツリーソートも安定ソートです。Haskell による 2-3木を使ったツリーソートの実装は以下のようになります。 (Java による実装をお望みの方は こちらのページ へどうぞ。ツリーソートではありませんが、 2-3木の実装のサンプルを示してあります)
まず、2-3木を使ったツリーソートの性能について言及しておきましょう。 2-3木を使ったツリーソートは今まで紹介してきたツリーソートの中では群を抜く性能を示します。赤黒木やAVL木では2-3木に太刀打ちできません。 それどころか、ボトムアップマージソート より高速です(乱数列で比較)。
乱数列のソート以外の性能もまずまずで、短い系列も速くソートでき、 整列済みの系列も、ボトムアップマージソートほどではありませんが高速にソートできます。ボトムアップマージソートのところでは、 ボトムアップマージソートが Haskell のソートの決定版かもと言いましたが、 どうやらそれを改める必要があるようです。
2-3木も普通はソートに使うというよりもマップ(連想配列)を実装するために使われます。 ここでは削除操作も含んだ2-3木によるマップの実装を見てみましょう。
ただし、削除操作は最下層のノードで開始されるものと見なして説明します。 内部ノードでの削除も最下層のノードでの削除に帰着できるからです。 内部ノードでの削除の具体的な説明はコードを読むことで代用してください。 基本的考え方は 赤黒木 や AVL木 と同じですが、 ノードが３分岐のときの処理が少し複雑です。 口で説明しても混乱すると思いますので、 コードで確認するのが一番と思います。 Haskell なんて分かんねーよ、という人は こちらのページ へどうそ。Java による実装を紹介しています。
以下に内部ノードでの削除の一例を示します。
赤で示した 7 の要素を削除するケースを示しています。 7 は最下層の要素ではないので左部分木があります。 そこで、青で示した左部分木の最大値 6 で 7 を置き換えます。 そして、元の 6 は削除します。 うまく2-3木の条件が維持されていることが分かると思います。 このように、内部ノードでの削除も最下層のノードでの削除に帰着できます。
さて、まずは３分岐のノードからの削除ですが、 これは単純に対象の要素と枝を削除して２分岐のノードにすることで完了です。 しかし、２分岐のノードから要素と枝を削除すると、 要素が無く枝が１つのノードになってしまって2-3木ではなくなります。 そこで、 この枝が１つのノードを削除時のアクティブなノードと見なして木を変形します。
削除のパターンはたくさんありますが、 基本となる考え方は全部同じです。それは、アクティブなノードと反応したら、 アクティブなノードの隣のノードから、余裕があれば、 つまり３分岐のノードだったら枝を１本分けてもらって、 アクティブなノードを２分岐のノードに変換するというものです。 隣のノードに余裕がない場合、つまり２分岐のノードだったら、 アクティブなノードと隣のノードを融合して３分岐のノードに変換します。 このとき、親ノードで枝が１つ減ることになるので、 場合によっては親ノードがアクティブなノードになります。 その場合、再帰的に上位のノードで変形を繰り返します。 そして、根がアクティブなノードになった場合は、 そのノードは余分なので切り詰めて、子ノードを新たな根にします。
それではまず、親ノードが２分岐の場合の削除パターンを示します。 通常のノードを四角で、アクティブなノードを丸で表します。 三角は部分木を表しています。
|
|
続いて、親ノードが３分岐の場合の削除パターンを示します。
|
|
|
|
ここで、具体的な削除の例を示しておきましょう。以下のようになります。
左端の赤で示したノードがアクティブなノードです。 要素が１つしか無い最下層のノードにおいて、 要素の削除を行うと生成されます。 アクティブなノードには要素がなく、枝は１本です。 アクティブなノードの隣のノード 2 は２分岐なので余裕がありません。 そこで、アクティブなノードと融合します。 すると、ノード 1 から枝が１つ減り、新たにアクティブなノードになります。 今度は、隣のノード 5,7 は３分岐なので余裕があります。 そこで、ノード 5,7 から枝を１本分けてもらいます。 すると、アクティブなノードは無くなり安定します。
もう１つ、アクティブなノードが根に到達した場合の例をあげておきます。 アクティブなノードの枝の数は１つなので、 余分に伸びていることになります。 そこで、アクティブなノードを切り詰めて、子ノードを新たな根にします。 このとき、木の高さが１段低くなることになります。
Haskell による2-3木の実装は以下のようになります。
さて、実は上記の T23Map.hs の show 関数はちょっとした力作です(^^;
2-3木を視覚的に分かりやすい文字列に変換します。
頭では分かっていても、
実際に2-3木が完全にバランスしている様子を見るのは感動的です。
それを確認するための簡単なチェックプログラムを書きました。
興味があれば実行してみてください。