Propel NestedSet créer arbre équilibré

Question

Je suis en train d'utiliser la fonction NestedSet Propel. Cependant, je me manque quelque chose sur l'insertion de telle sorte que l'arbre est équilibré car il est créé (à savoir le remplir horizontalement).

Dire que j'ai ces éléments:

       root
  r1c1      r1c2
r2c1 r2c2

Je veux insérer r2c3 comme le 1er enfant de R1C2 (à savoir remplir la ligne 2 avant de commencer la ligne 3).

Mon premier coup de couteau à c'était de créer cette fonction:

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

Toutefois, cela insérera un enfant sur R2C1, plutôt à R1C2 que je veux.

Y at-il un moyen d'insérer une entrée dans l'arborescence à la prochaine place disponible en quelque sorte?

TIA Mike

Answer 1

OK, grâce à http://mikehillyer.com/articles/ la gestion hiérarchique des données-en-mysql / , je trouve que cet algorithme va faire ce que je veux:

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

Il exécute essentiellement ce 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

Une feuille a DROITE GAUCHE = + 1, un noeud avec 1 enfant DROITE GAUCHE = + 3. En ajoutant la clause ORDER BY u.PARENT_ID, on trouve le nœud le plus élevé dans l'arbre disponible. Si vous utilisez LEFT_ID ou RIGHT_ID, il ne balance pas l'arbre.