Fertile Forest Model (9/n) ノード削除

ノードの削除

ツリー構造データにおけるノード削除には、次の 3種類があります。

1. 指定ノードを部分木ごと削除する
2. 指定ノードの子孫ノードだけ削除する
3. 指定ノードを削除して、その子孫ノードを繰り上げる

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

指定ノードを部分木ごと削除する

指定ノードを部分木ごと削除するクエリは、部分木の検索クエリの WHERE 句がそのまま使えます。以下は、[B] の部分木ノードの削除文です。

DELETE
  FROM ff_tables
  WHERE ff_queue >= 1
    AND ff_queue <=
      COALEPSE(
        (SELECT MIN(ff_queue) - 1
          FROM ff_tables
          WHERE ff_queue > 1 AND ff_depth <= 1
        ),
        0x7fffffff
      )
;

指定ノードの子孫ノードだけ削除する

指定ノードの子孫ノードだけ削除するのも、部分木クエリと同じく検索クエリの応用で簡単に実装できます。以下は、 [B] の子孫ノードの削除文です。

DELETE
  FROM ff_tables
  WHERE ff_queue > 1
    AND ff_queue <=
      COALEPSE(
        (SELECT MIN(ff_queue) - 1
          FROM ff_tables
          WHERE ff_queue > 1 AND ff_depth <= 1
        ),
        0x7fffffff
      )
;

指定ノードを削除して、その子孫ノードを繰り上げる

指定ノードを削除してその子孫ノードを繰り上げるのは少し煩雑です。指定ノードを削除する DELETE 文と子孫ノードを繰り上げるための UPDATE 文を発行する必要があります。

以下は、 [B] を削除して [B] の子孫ノードを繰り上げる手順です。

mysql> BEGIN;

mysql> DELETE
  FROM ff_tables
  WHERE ff_queue = 1
;

mysql> UPDATE ff_tables
  SET ff_depth = ff_depth - 1
  WHERE ff_queue > 1
    AND ff_queue <=
      COALEPSE(
        (SELECT MIN(ff_queue) - 1
          FROM ff_tables
          WHERE ff_queue > 1 AND ff_depth <= 1
        ),
        0x7fffffff
      )
;

mysql> COMMIT;