ノードの移動
ある子ノードを別の親ノードの子として移動させるのは、 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 を附番し直すコストがかかります。これも、入れ子集合モデルが抱えているのと同じ難題です。
拙作のライブラリでは、ノード追加時のコストを軽減するための工夫が実装されています。その工夫に於いては、ノード移動時のコストは「移動するノードのサブツリーのみ」になります。つまり、コストは最小限で抑えられるケースがあるというわけです。
工夫の方法について記すと、それだけで膨大な記載になってしまいます。興味がある方は、以下の拙作ライブラリを解読してみて下さいな。