且听疯吟 / 预排序遍历算法树

mptt

1. 预排序遍历树算法

mptt (Modified Preorder Tree Traversal)¹
优点
查询效率高，只需要一次查询即可获得层级结构中某个节点的所有子节点，无需递归查询
缺点
插入、删除、移动节点效率较低
适用
在传统关系数据库中实现层级树结构
- 读压力 > 写压力， mptt 算法可以提高效率
- 写压力 > 读压力，使用传统的邻接表 (adjacency list model)

2. 增删查改

Create

假设增加的节点为 c, 该节点前一节点为 p
节点 c 左值为 p 的右值 +1，右值为 p 右值 +2
所有左值大于节点 c 的左值的节点，其左值均 +2
所有右值大于节点 c 的右值的节点，其右值均 +2
写入节点 c 到数据库

SELECT @cRight := rgt FROM mptt	WHERE name = 'p';
UPDATE mptt SET rgt = rgt + 2 WHERE rgt > @cRight ;
UPDATE mptt SET lft = lft + 2 WHERE lft > @cRight ;
INSERT INTO mptt(name, lft, rgt) VALUES('c', @cRight+ 1, @cRight+ 2);

Read
- 查询节点 c 的子节点：
  - 查询所有左值大于 c 的左值且右值小于 c 的右值的节点
```
SELECT * FROM mptt WHERE lft BETWEEN @cLeft and @cRight;
```
- 查询节点 c 的父节点：
  - 查询所有左值小于 c 的左值且右值大于 c 的右值(或左值)的节点
```
SELECT * FROM mptt WHERE lft < @cLeft and rgt > @cLeft;
```
- 节点 c 的子节点个数：
  - (c.right - c.left - 1) / 2
Update
移动节点即：
- 删除节点
- 在指定位置新增节点

Delete

删除节点 c
所有右值大于 c 右值的节点，右值 -2
所有左值大于 c 左值的节点，左值 -2

DELETE FROM mptty WHERE lft BETWEEN @cLeft AND @cRight;
UPDATE mptt SET rgt = rgt - 2 WHERE rgt > @cRight;
UPDATE mptt SET lft = lft - 2 WHERE lft > @cLeft;

3. 重建树结构

很容易推断，对排序好的 mptt tree，仅需要一次遍历，即可根据所有节点的左右值记录重建树结构
以 python 为例：

# Node class
class Node(object):

    def __init__(self, left, right):
        super(Node, self).__init__()
        self.left = left
        self.right = right
        self.depth = 1
        self.children = []

 # arg: Node List
 def rebuild(l):
		# 节点按左值排序，即遍历顺序
        l.sort(key=lambda x: x.left)

		# 使用列表暂存每层子树的父节点
        # 如 pi[0] 表示第 2 层的节点的父节点在 l 中的 index
        pi = [0]

        for i, c in enumerate(l):
            if c.left != 1:
                p = l[i - 1]

                # 使用 c 表示此节点，p 表示 c 的前一节点
                # 如果连续的两个节点 c 和 p 的左值增加幅度为 1，则说明其深度增加了 1
                # 且 p 为 c 及 c 的兄弟节点的父节点
                if c.left == p.left + 1:
                    c.depth = p.depth + 1
                    if c.depth - 1 > len(pi):
                        pi.append(i - 1)
                    else:
                        pi[c.depth - 2] = i - 1

                # 如果 c 的左值大于 p 的父节点的右值，则说明 p 与 c 并非兄弟节点
                # 并可以计算出两节点的深度差为 c 的左值与 p 的右值之差减 1
                elif c.left > l[pi[p.depth - 2]].right:
                    c.depth = p.depth - (c.left - p.right - 1)

                # 不满足以上两个条件，说明 c 是 p 的兄弟节点
                else:
                    c.depth = p.depth

			    # 将 c 作为 pi 中记录的父节点的子节点
                l[pi[c.depth - 2]].children.append(c)

        return l

Update

完整代码及生成 Json 和基于 D3.js² 的树状图：
https://gist.github.com/caoyue/704e472215af29b08a27