Todavía estoy pensando, pero mucho más rápido que atravesar el árbol sería un position_id para cada posición posible. Si observa un árbol completo de cierto nivel, verá lo que quiero decir:su ejemplo se ve así.
Las conexiones entre position y position_id son algo con aritmética int simple (div y módulo).
Todos los nodos en un subárbol comparten algunas de esas propiedades; por ejemplo, los subnodos directos del nodo 4 (tercer nodo en la segunda fila) son 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
Así que aún tendría que atravesar los niveles en un bucle, pero no los nodos si maneja ese número de posición en cada nodo.
Paso 2:
La fila r tiene 5^r elementos (comenzando con la fila 0).
Almacene en cada nodo la fila y la columna, en cada fila la columna comienza con 0. Entonces, la segunda fila no es 2,3,4,5,6 sino 1|0, 1|1, 1|2, 1| 3, 1|4.
Si su raíz de búsqueda es 1|1 (fila 1, segundo elemento, en su bonito árbol llamado "3"), entonces todos los niños en la fila 2 tienen
col / 5 = 1
todos los niños en la fila 3 tienen
col / 25 = 1
y así sucesivamente.
Un nivel por debajo del nodo 2|10 son los nodos 3|(5*10) hasta 3|(5*11-1) =50 .. 55-1
dos niveles por debajo son los nodos 4|(50*5) hasta 4|(55*5-1)
y así sucesivamente.
Paso 3
Pseudocó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
}
Pregunte si necesita más detalles.
