Ainda estou pensando, mas muito mais rápido do que percorrer a árvore seria um position_id para todas as posições possíveis. Se você olhar para uma árvore completa de um certo nível, verá o que quero dizer - seu exemplo se parece com isso.
As conexões entre position e position_id são algo com simples aritmética int (div e módulo).
Todos os nós em uma subárvore compartilham algumas dessas propriedades - por exemplo, os subnós diretos do nó 4 (terceiro nó na segunda linha) são números
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
Portanto, você ainda teria que percorrer os níveis em um loop, mas não os nós se gerenciar esse número de posição em cada nó.
Etapa 2:
A linha r tem 5^r elementos (começando com a linha 0).
Armazene em cada nó a linha e a coluna, em cada linha a coluna começa com 0. Então a segunda linha não é 2,3,4,5,6 mas é 1|0, 1|1, 1|2, 1| 3, 1|4.
Se sua raiz de pesquisa for 1|1 (linha 1, segundo elemento, em sua bela árvore chamada "3"), todos os filhos na linha 2 terão
col / 5 = 1
todas as crianças na linha 3 têm
col / 25 = 1
e assim por diante.
Um nível abaixo do nó 2|10 são os nós 3|(5*10) até 3|(5*11-1) =50 .. 55-1
dois níveis abaixo são os nós 4|(50*5) até 4|(55*5-1)
e assim por diante.
Etapa 3
Pseudo-código:
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
}
Por favor, pergunte se são necessários mais detalhes.
