データ構造におけるソリッドツリー(実線木)とは?基本概念と仮想木の構造

ソリッドツリー(実線木)の基本概念

与えられた森(forest)に対して、一部の辺を「破線(dashed)」に、残りを「実線(solid)」として扱います。各非葉ノードは、その子のうちただ一つだけを実線の辺で結び、それ以外の子はすべて破線の辺で接続します。

より具体的には、どの木においても「右端の子」へのリンクを実線で保持し、その他の子へのリンクはすべて「破線」として作成します。

木の分解と仮想木(virtual tree)

この操作の結果、木は複数の実線パス(solid path)の集合へと分解されます。実線パスの根どうしは、破線の辺によって別の実線パスと接続されます。

ここで、「仮想木(virtual tree)」と呼ばれる新たなデータ構造が構築されます。リンク・カット操作の対象となる各木 T は、同じノード集合を含む仮想木 V によって表現されます。ただし、元の木における各実線パスは、仮想木では二分木へと変換され、この二分木は可能な限り平衡(balanced)な形に保たれます。

したがって、仮想木の各ノードは、(実線の)左の子、(実線の)右の子、そして 0 個以上の(破線の)中間子(middle children)を持ちます。

仮想木の構造と親ノードの決まり方

言い換えれば、仮想木とは「破線の辺で連結された実線二分木の階層構造」です。各ノードは、親へのポインタ、および左の子・右の子へのポインタを保持します。

各パスは二分木へ変換されます。パス内のノード p の親 q は、実線木における p の中順(in-order/対称順)での後続ノードになります。ただし、p がその実線部分木内で対称順の最後のノードである場合は、p を含む実線部分木の根の親が、その親パスとなります。

Formally, Parentpath(v) = Node(Inorder(v) + 1)

中順と祖先・子孫の関係

任意のノード v について、左部分木内のすべてのノードは v より小さい中順番号を持ち、右部分木内のノードはより大きい中順番号を持ちます。この性質により、左部分木のノードはすべて「子孫」、右部分木のノードはすべて「祖先」として扱うことができます。

つまり、二分木における左の子の親は、元の木では「祖先」とみなされ、逆に二分木における右の子の親は、元の木では「子孫」とみなされます。この順序規約によって、コスト追加(add cost)処理を効率的に実行できるのです。

mincost と δ フィールドの定義

話を進めるために、いくつかの定義と記法を導入します。

mincost(x):x と同じ実線部分木内にある x のすべての子孫の中で、最小キー値を持つノードのコストを表します。

そして、各ノードには δcost(x) と δmin(x) という 2 つのフィールドを格納します。定義は次の通りです。

δmin(x) = cost(x) − mincost(x)

δcost(x) = cost(x) − cost(parent(x))  (x が実線の親を持つ場合)
δcost(x) = cost(x)                    (それ以外:x は実線木の根として扱う)