推动 NestedSet 创建平衡树

Question

我正在尝试使用 Propel 的 NestedSet 功能。但是，我缺少一些有关插入的内容，以便树在创建时保持平衡（即水平填充）。

假设我有这些元素：

       root
  r1c1      r1c2
r2c1 r2c2

我想插入 r2c3 作为 r1c2 的第一个子元素（即在开始第 3 行之前填充第 2 行）。

我的第一个尝试是创建这个函数：

function where(User $root,$depth=0)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;
  foreach($root->getChildren() as $d)
  {
    if ( $d->getNumberOfChildren() < 2 )
    {
      return $d;
    }
  }
  foreach($root->getChildren() as $d)
  {
    return where($d, $depth+1);
  }
}

但是，这将在 r2c1 上插入一个子项，而不是像我想要的那样在 r1c2 上插入一个子项。

有没有办法以某种方式将条目插入树中的下一个可用位置？

TIA 麦克风

Answer 1

好的，感谢 http://mikehillyer.com/articles/managing-hierarchical -data-in-mysql/，我发现这个算法会做我想要的事情：

function where($root)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;

  $finder = DbFinder::from('User')->
    where('LeftId','>=',$root->getLeftId())->
    where('RightId','<=',$root->getRightId())->
    whereCustom('user.RightId = user.LeftId + ?',1,'left')->
    whereCustom('user.RightId = user.LeftId + ?',3,'right')->
    combine(array('left','right'),'or')->
    orderBy('ParentId');
    return $finder->findOne();
}

它基本上执行这个SQL：

SELECT u.*
FROM user u
WHERE u.LEFT_ID >= $left AND u.RIGHT_ID <= $right AND
  (u.RIGHT_ID = u.LEFT_ID+1 OR u.RIGHT_ID = u.LEFT_ID+3)
ORDER BY u.PARENT_ID
LIMIT 1

叶子有RIGHT=LEFT+1，有1个子节点的节点有RIGHT=LEFT+3。通过添加 ORDER BY u.PARENT_ID，我们找到树中可用的最高节点。如果使用 LEFT_ID 或 RIGHT_ID，则不会平衡树。