Sto ancora pensando, ma molto più veloce che attraversare l'albero sarebbe un position_id per ogni possibile posizione. Se guardi un albero completo di un certo livello vedresti cosa intendo:il tuo esempio è simile a quello.
Le connessioni tra position e position_id sono qualcosa con una semplice aritmetica int (div e modulo).
Tutti i nodi in un sottoalbero condividono alcune di queste proprietà, ad esempio i sottonodi diretti del nodo 4 (terzo nodo nella seconda riga) sono numeri
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
Quindi dovresti comunque attraversare i livelli in un ciclo, ma non i nodi se gestisci quel numero di posizione in ogni nodo.
Fase 2:
La riga r ha 5^r elementi (a partire dalla riga 0).
Memorizza in ogni nodo la riga e la colonna, in ogni riga la colonna inizia con 0. Quindi la seconda riga non è 2,3,4,5,6 ma è 1|0, 1|1, 1|2, 1| 3, 1|4.
Se la tua radice di ricerca è 1|1 (riga 1, secondo elemento, nel tuo bell'albero chiamato "3"), allora tutti i bambini nella riga 2 hanno
col / 5 = 1
tutti i bambini della riga 3 hanno
col / 25 = 1
e così via.
Un livello sotto il nodo 2|10 sono i nodi 3|(5*10) fino a 3|(5*11-1) =50 .. 55-1
due livelli sotto sono i nodi 4|(50*5) fino a 4|(55*5-1)
e così via.
Fase 3
Pseudocodice:
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
}
Si prega di chiedere se sono necessari maggiori dettagli.
