9

我一直在考虑改进的前序树遍历算法，用于将树存储在平面表中（例如 SQL）。

我不喜欢标准方法的一个属性是，要插入一个节点，您必须（平均）触摸 N/2 个节点（左或右高于插入点的所有节点）。

我见过的实现依赖于顺序编号的值。这样就没有更新的余地了。

这似乎不利于并发和扩展。想象一下，您有一个植根于世界的树，其中包含大型系统中每个帐户的用户组，它非常大，以至于您必须将树的子集存储在不同的服务器上。触摸所有节点的一半以将节点添加到树的底部是不好的。

这是我正在考虑的想法。基本上通过对键空间进行分区并在每个级别进行划分来为插入留出空间。

这是一个 N max = 64 的示例（这通常是数据库的 MAX_INT）

                     0:64
              ________|________
             /                 \
         1:31                   32:63
        /    \                 /     \
    2:14    15-30         33:47       48:62

在这里，一个节点被添加到树的左半部分。

                     0:64  
              ________|________
             /                 \
         1:31                  32:63
      /   |   \               /     \
  2:11  11:20  21:30     33:47       48:62

插入和删除过程必须扩展该算法，以递归地重新编号到子树的左/右索引。由于查询节点的直接子节点很复杂，我认为将父 ID 也存储在表中是有意义的。然后算法可以选择子树（使用 left > p.left && right < p.right），然后使用 node.id 和 node.parent 遍历列表，细分索引。

这比仅仅增加所有索引为插入腾出空间（或减少删除）更复杂，但它有可能影响更少的节点（仅插入/删除节点的父节点的后代）。

我的问题基本上是：

  1. 这个想法是否已经正式化或实施了？

  2. 这与嵌套间隔相同吗？

4

3 回答 3

5

我以前听说过有人这样做，出于同样的原因，是的。

请注意，这样做确实会失去算法的几个小优势

  • 通常，您可以通过 ((right - left + 1) div 2) 来判断节点的后代数量。这有时会很有用，例如，如果您要在树视图中显示计数，该计数应包括在树中进一步向下找到的子项的数量
  • 从上面开始，很容易选择所有叶节点——WHERE（右=左+1）。

这些都是相当小的优势，可能对您没有用处，尽管对于某些使用模式，它们显然很方便。

也就是说，正如上面所建议的，听起来物化路径可能对您更有用。

于 2009-06-28T21:01:00.743 回答
2

我认为你最好看看另一种储存树木的方式。如果您的树很宽但不是很深（对于您建议的情况似乎很可能），您可以将完整的祖先列表存储到每个节点的根。这样，修改节点不需要接触除被修改节点之外的任何节点。

于 2009-06-27T10:40:20.770 回答
1

你可以将你的表一分为二：第一个是（节点 ID，节点值），第二个是（节点 ID，子 ID），它存储了树的所有边。然后插入和删除变成 O（树深度）（你必须导航到元素并修复它下面的内容）。

您提出的解决方案看起来像B-tree。如果您可以估计树中的节点总数，那么您可以预先选择树的深度。

于 2009-06-26T15:53:50.610 回答