2010-06-04

入れ子集合モデルのノードの入れ替え

CakePHPのTreeBehaviorを使っているModelで部分木を入れ替える必要があったので SQLで木と階層構造のデータを扱う(1)―― 入れ子集合モデル 3-5.ノードを入れ替える のクエリを使わせてもらったんですが、動作のイメージがつかなかったので自分なりにまとめてみました。

クエリ

--部分木を入れ替える
UPDATE OrgChart
   SET lft = CASE WHEN lft BETWEEN :lft_1 AND :rgt_1 -- (1)
                    THEN :rgt_2 + lft - :rgt_1 
                  WHEN lft BETWEEN :lft_2 AND :rgt_2 -- (2)
                    THEN :lft_1 + lft - :lft_2
                  WHEN lft BETWEEN :rgt_1 + 1 AND :lft_2 - 1 -- (3)
                    THEN :lft_1 + :rgt_2 + lft - :rgt_1 - :lft_2 
                  ELSE lft END, -- (4)
       rgt = CASE WHEN rgt BETWEEN :lft_1 AND :rgt_1
                    THEN :rgt_2 + rgt - :rgt_1
                  WHEN rgt BETWEEN :lft_2 AND :rgt_2
                    THEN :lft_1 + rgt - :lft_2
                  WHEN rgt BETWEEN :rgt_1 + 1 AND :lft_2 - 1
                    THEN :lft_1 + :rgt_2 + rgt - :rgt_1 - :lft_2 
                  ELSE rgt END
 WHERE lft BETWEEN :lft_1 AND :rgt_2
   AND :lft_1 < :rgt_1
   AND :rgt_1 < :lft_2
   AND :lft_2 < :rgt_2;

ケースごとの動作

(※lftもrgtもやっていることは同じなのでxとします。(1)などの番号は上記クエリにコメントしたものに対応します)

  • (1). 対象ノードが左ノード内にある、または左ノード自身の場合: ノードを右に移動するために、左ノードと右ノードの位置の差の分、対象ノードの位置を右にずらす
    • x = x + (rgt_2-rgt_1) と同じ
    • (添字に歯抜けのある場合、左端を基準にしたlft_2-lft_1だと他のノードとの位置関係がおかしくなる可能性がある)
  • (2). 対象ノードが右ノード内にある、または右ノード自身の場合: ノードを左に移動するために、左ノードと右ノードの位置の差の分、対象ノードの位置を左にずらす
    • x = x - (lft_2-lft_1) と同じ
    • (添字に歯抜けのある場合、右端を基準にしたrgt_2-rgt_1だと他のノードとの位置関係がおかしくなる可能性がある)
  • (3). 対象ノードが左ノードと右ノードの間にある場合: 左右ノードのサイズの違う分のノードの位置をずらす
    • x = x + (右ノードサイズ - 左ノードサイズ)
         = x + ((rgt_2-lft_2) - (rgt_1-lft_1)) と同じ
  • (4). (1)(2)(3)どれにも当てはまらない場合: 更新する必要がないので更新しない

上記のようにA(2, 7)とB(10, 13)の部分木を入れ替える場合、

  • A: ケース(1)のためrgt_2 - rgt_1 = 13 - 7 = 6を加算してA(8, 13)
    • A内のノードもそれぞれ6加算
  • B: ケース(2)のためlft_2 - lft_2 = 10 - 2 = 8を減算してB(2, 5)
    • B内のノードもそれぞれ8減算
  • C: ケース(3)のため(rgt_2 - lft_2) - (rgt_1 - lft_1) = (13-7) - (10-2) = -2を加算してC(6, 7)