Je pense toujours, mais beaucoup plus rapide que de traverser l'arbre serait un position_id pour chaque position possible. Si vous regardez un arbre complet d'un certain niveau, vous verrez ce que je veux dire - votre exemple ressemble à ça.
Les connexions entre position et position_id sont quelque chose avec une simple arithmétique int (div et modulo).
Tous les nœuds d'un sous-arbre partagent certaines de ces propriétés - par exemple, les sous-nœuds directs du nœud 4 (troisième nœud de la deuxième ligne) sont des nombres
1 + 5 + (3-1)*5 + 1
1 + 5 + (3-1)*5 + 2
1 + 5 + (3-1)*5 + 3
1 + 5 + (3-1)*5 + 4
1 + 5 + (3-1)*5 + 5
Vous devrez donc toujours traverser les niveaux dans une boucle, mais pas les nœuds si vous gérez ce numéro de position dans chaque nœud.
Étape 2 :
La ligne r contient 5^r éléments (en commençant par la ligne 0).
Stockez dans chaque nœud la ligne et la colonne, dans chaque ligne la colonne commence par 0. Ainsi, la deuxième ligne n'est pas 2,3,4,5,6 mais est 1|0, 1|1, 1|2, 1| 3, 1|4.
Si votre racine de recherche est 1|1 (ligne 1, deuxième élément, dans votre bel arbre nommé "3"), alors tous les enfants de la ligne 2 ont
col / 5 = 1
tous les enfants de la rangée 3 ont
col / 25 = 1
et ainsi de suite.
Un niveau en dessous du nœud 2|10 sont les nœuds 3|(5*10) jusqu'à 3|(5*11-1) =50 .. 55-1
deux niveaux en dessous sont les nœuds 4|(50*5) à 4|(55*5-1)
et ainsi de suite.
Étape 3
Pseudo-code :
getFreeNode($node){
$rowMax = 100;
$row = $node->row + 1;
$from = 5 * $node->col;
$to = $from + 5;
while($row <= $rowMax){
if ($id = query("select id from member "
."where row = $row and col >= $from and col < $bis"
." and empty_position > 0"))
{
return $id;
}
$row++;
$from *= 5;
$to *= 5;
}
}
insertNode($parent, $node){
$node->row = $parent->row + 1;
$node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
$node->parent_id = $parent->member_id
}
Veuillez demander si plus de détails sont nécessaires.
