且听疯吟 在此记录扯淡的青春
预排序遍历算法树

mptt

1. 预排序遍历树算法

  • mptt (Modified Preorder Tree Traversal)1
  • 优点

    查询效率高,只需要一次查询即可获得层级结构中某个节点的所有子节点,无需递归查询

  • 缺点

    插入、删除、移动节点效率较低

  • 适用

    在传统关系数据库中实现层级树结构

    • 读压力 > 写压力, 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.js2 的树状图:
https://gist.github.com/caoyue/704e472215af29b08a27