ノードの移動

ある子ノードを別の親ノードの子として移動させるのは、 FF モデルでは意外に簡潔に実装できます。事前の計算が必要ですが、いかなる移動処理も UPDATE 一回で行えます。

DEPTH|
     |
   0 | [A]--+-----------+
     |      |           |
   1 |     [B]--+---+  [C]--+---+
     |          |   |       |   |
   2 |         [D] [E]     [F] [G]--+---+
     |                              |   |
   3 |                             [H] [I]
-----+-------------------------------------------
     |  0   1   2   3   4   5   6   7   8   QUEUE

範囲入れ替え

ノード [G] を [E] の子ノードに移動させる例で説明してみます。

移動先の新しい親ノード [E] の QUEUE は 3

移動させる部分木は、 [G] ～ [I]

[E] と [G] の間にあるノードは、移動させる部分木のノード数の 3個分スライドさせる

[E] と [G] の DEPTH をそれぞれ Ed, Gd とした時、移動させる部分木全体の DEPTH は (Ed - Gd + 1) だけずれる

QUEUE に関する移動処理は、下図で「 (2) と (3) の範囲を入れ替えて QUEIE と DEPTH を附番し直す」と要約されます。

DEPTH|
     |
   0 | [A]--+-----------+
     |      |           |
   1 |     [B]--+---+  [C]--+---+
     |          |   |       |   |
   2 |         [D] [E]     [F] [G]--+---+
     |                              |   |
   3 |                             [H] [I]
-----+-------------------------------------------
     |  0   1   2   3   4   5   6   7   8   QUEUE
                    *   *---*   *-------*
                   (1)   (3)       (2)

DEPTH|
     |
   0 | [A]--+-----------------------+
     |      |                       |
   1 |     [B]--+---+              [C]--+
     |          |   |                   |
   2 |         [D] [E]--+              [F]
     |                  |
   3 |                 [G]--+---+
     |                      |   |
   4 |                     [H] [I]
-----+-------------------------------------------
     |  0   1   2   3   4   5   6   7   8   QUEUE
                    *   *-------*   *---*
                   (1)     (2)       (3)

前方へ移動する場合と後方へ移動する場合で QUEUE の計算が少し変わりますが、基本的な考え方は同じです。

ノード移動のコストカット

原始的 FFモデルでは、移動先のノードが離れていれば離れているほど QUEUE を附番し直すコストがかかります。これも、入れ子集合モデルが抱えているのと同じ難題です。

拙作のライブラリでは、ノード追加時のコストを軽減するための工夫が実装されています。その工夫に於いては、ノード移動時のコストは「移動するノードのサブツリーのみ」になります。つまり、コストは最小限で抑えられるケースがあるというわけです。

工夫の方法について記すと、それだけで膨大な記載になってしまいます。興味がある方は、以下の拙作ライブラリを解読してみて下さいな。

リンク