代码之家 › 专栏 › 技术社区 › Mike Crowe

推进嵌套集创建平衡树

nested-sets propel symfony1

0

Mike Crowe · 技术社区 · 15 年前

我正在尝试使用推进的嵌套功能。但是,我缺少一些关于插入的内容,这样树在创建时就保持平衡(即水平填充)。

假设我有这些元素:

       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上插入一个子项。

是否有办法在下一个可用位置插入一个条目到树中?

蒂亚迈克

1 回复 | 直到 15 年前

1

0

Mike Crowe 15 年前

好的,谢谢 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,我们可以找到树中可用的最高节点。如果你使用左\u id或右\u id,它不会平衡树。