ノードの移動
ある子ノードを別の親ノードの子として移動させるのは、 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 の計算が少し変わりますが、基本的な考え方は同じです。
参照整合性の破損可能性
移動時の UPDATE が一回しか発行されないため、破損可能性はかなり低くなっています。