The Cusp of Helix

Fertile Forest Model

ノードの移動

ある子ノードを別の親ノードの子として移動させるのは、 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] の子ノードに移動させる例で説明してみます。

  1. 移動先の新しい親ノード [E] の QUEUE は 3
  2. 移動させる部分木は、 [G] ~ [I]
  3. [E] と [G] の間にあるノードは、移動させる部分木のノード数の 3個分スライドさせる
  4. [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 が一回しか発行されないため、破損可能性はかなり低くなっています。