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);
  }
}

ただし、これにより、必要に応じて r1c2 ではなく、r2c1 に子が挿入されます。

どういうわけか、次の利用可能な場所でエントリをツリーに挿入する方法はありますか?

ティア・マイク

4

1 に答える 1

0

OK、 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 を使用すると、ツリーのバランスが取れなくなります。

于 2009-11-12T20:09:57.837 に答える