Propel NestedSet создает сбалансированное дерево

Question

Я пытаюсь использовать функцию Propel NestedSet. Тем не менее, я что-то упускаю при вставке так, что дерево сбалансировано при его создании (то есть заполняется горизонтально).

Скажем, у меня есть эти элементы:

       root
  r1c1      r1c2
r2c1 r2c2

Я хочу вставить r2c3 в качестве первого дочернего элемента r1c2 (то есть заполнить строку 2, прежде чем начинать с строки 3).

Моя первая попытка была создать эту функцию:

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, как я хочу.

Есть ли способ как-нибудь вставить запись в дерево в следующем доступном месте?

ТИА Майк

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, это не уравновешивает дерево.