2-3木と平面走査法の複雑度

平面走査法で要求されるデータの処理

平面走査法では2つのデータ列AとBを使いました。Aというのは走査直線と今クロスしている線分を、Bというのはイベントを格納しているデータ列でしたね。

さて、まずAに行われる操作は次の通りです。
1)挿入⇒左端点イベント
2)削除⇒右端点イベント
3)交換⇒交点イベント

また、Bに行われる操作は次の通りです。
1)挿入・検索⇒交点イベント
2)削除⇒右端点イベント
検索というのは前に説明してなかったですが、『新しく見つかった交点pがすでに発見されたものかどうかを確認』するものです。

これらのすべての操作を出来るようなデータ構造として2-3木というものがあります。

2-3木

次のような性質を持つ木を2-3木と言います。
1)葉の深さがすべて同じ
2)葉でない頂点はすべて2個か3個の子を持つ。
2個の子を持つ頂点について、その子は『左から』順番に第一番目の子を左の子といい、二番目の子を中央の子と言います。
また、3個の子を持つ頂点については左から、「左の子」「中央の子」「右の子といいます。

高さの2-3木の葉の数は以上以下になります。
っていうのはすべての葉でない頂点が2個の子ノードを持つとき、っていうのは3個の子ノードを持つときですね。
したがって葉の数をとすれば深さのオーダーは

となります。

2-3木における葉の削除

3つ子の葉の1つを削除したとしてもまだ2つの葉が残っていますので、2-3木の条件は保たれます。
問題は2つ子の葉の片方を削除するときです。この場合何も考えずに子を削除してしまうと葉の数が足りなくなってしまうので、削除後のアフターケアが必要になります。
そのような後処理は葉の兄弟にしてもらうことになりますが、その兄弟の子供の数によって後処理の手続きは変わってきます。

まず隣が3つ子のとき、灰色の葉の削除を考えます。

このときまずは削除をしてみると次のように葉の数が足りなくなります。

なので兄弟の『一番左の子を』おひとり分けてもらいます。

これで2-3という形は保持されます。

次に兄弟が2つ子のとき同じように削除してみます。

やっぱり兄弟から一人…と行きたいところですが、取ってくる先も2人しかいないので一人頂くというわけにはいきません。

そこで、2人の親を合体して無理やり3つ子に持っていきます。

これで2-3木をちゃんと復元できました。

…さて、お気づきの方もいるかもしれませんが。2人の親にはさらにその親がいるはずです。
葉にとっては『2人の親の合体』ですが、親の親（ここでは祖父とでも言っておきましょう）にとっては『2人の子の合体』です。
つまり、もし祖父が2人しか子供を持っていなかったら、その祖父の子は1人になってしまいます。

こうなった場合の修復の仕方は上と同じです。
つまり、祖父の子であり、合体した親の兄弟であるノードを一つ、取ってくればいいのです。
この連鎖が根にまでいってしまって、根の子が1人だけになった場合。この場合はその根を削除してやって、唯一の子に根の座を継承してやれば万事解決です。

2-3木における葉の追加

葉をある場所に追加したいときの問題は子が4つになってしまうことですね。
この場合は4人の子を持つ親を分裂させて、2つずつ子供を持たせることによって解決すればよいです。

子供を分裂させた結果祖父が4人の子を持ってしまうのならば、その祖父を2人に分割してやればいいです。
この連鎖が根にまで行ってしまって、根の子が4人になってしまった場合。この場合はその根を2つに分割して、それら2人の親を新たに作ってやれば解決です。

2-3木を使った平面走査法の処理

前前項であげた処理を行うために、次のような下準備をします。

例えばBについて、初めの段階で端点の値が入っています。
この端点はすべてx座標値を持っていますので、これらの端点をx座標順に左からずらっと並べてみます。

これから2-3木を作っていきます。2個か3個の葉を子とする親ノードを作っていけばいいわけですね。
ここで、新しく作った親ノードには2つの値を格納します。
1つは『左の子を根とした木の最大値』、もう一つは『中央の子を根としたときの木の最大値』です。
まず1個親を作った状態が以下になります。この場合子は葉なのでそのまま左の子と中央の子の値を入れればいいですね。

こんな調子で続けていくと次のようになります。

さて、なんでこんな木を作ったかというと、根からたどることで所望のところに葉を挿入したり、所望の葉を削除したりできるからです。
例えば『12』を挿入したいとき。左の木の最大値は9であると根に描いてあるので左の木に進みます。
また『12』は9以上14以下なので、左の子に進みます。したがって『11,14』という親に進めるので、この中央の子として『12』を挿入すればよいのです。
このようにしていきたいところに各頂点の比較を行っていくことでたどり着けるので、『挿入』『削除』『検索』といった処理は木の深さで可能です。