Impulsar la creación de NestedSet árbol equilibrado

Question

Estoy tratando de utilizar la función de NestedSet de Propel. Sin embargo, me falta algo acerca de la inserción de tal manera que el árbol está equilibrado, ya que se crea (es decir, llenarlo en sentido horizontal).

Digamos que tiene estos elementos:

       root
  r1c1      r1c2
r2c1 r2c2

Quiero insertar r2c3 como la primera niño de R1C2 (es decir, llenar la fila 2 antes de comenzar en la fila 3).

Mi primer intento en esta era crear esta función:

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

Sin embargo, se insertará un niño en R2C1, R1C2 más bien a lo que quiera.

¿Hay una manera de insertar una entrada en el árbol en el siguiente lugar disponible alguna manera?

TIA Mike

Answer 1

Bien, gracias a http://mikehillyer.com/articles/ gestión jerárquica-datos-en-mysql / , he encontrado que este algoritmo hará lo que yo quiero:

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

Básicamente ejecuta este 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

Una hoja tiene DERECHA IZQUIERDA = + 1, un nodo con 1 niño tiene DERECHA IZQUIERDA = + 3. Al añadir el ORDER BY u.PARENT_ID, nos encontramos con el nodo más alto en el árbol disponibles. Si utiliza LEFT_ID o RIGHT_ID, que no equilibra el árbol.