0

我正在尝试使用 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 迈克

4

1 回答 1

0

好的，感谢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

A leaf has RIGHT=LEFT+1, A node with 1 child has RIGHT=LEFT+3. By adding the ORDER BY u.PARENT_ID, we find the highest node in the tree available. If you use LEFT_ID or RIGHT_ID, it does not balance the tree.

于 2009-11-12T20:09:57.837 回答