Ich denke immer noch, aber viel schneller als das Durchqueren des Baums wäre eine position_id für jede mögliche Position. Wenn Sie sich einen vollständigen Baum einer bestimmten Ebene ansehen, würden Sie sehen, was ich meine - Ihr Beispiel sieht so aus.
Die Verbindungen zwischen position und position_id sind etwas mit einfacher int-Arithmetik (div und modulo).
Alle Knoten in einem Unterbaum haben einige dieser Eigenschaften gemeinsam – zum Beispiel sind die direkten Unterknoten von Knoten 4 (dritter Knoten in der zweiten Reihe) Nummern
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
Sie müssten also immer noch die Ebenen in einer Schleife durchlaufen, aber nicht die Knoten, wenn Sie diese Positionsnummer in jedem Knoten verwalten.
Schritt 2:
Zeile r hat 5^r Elemente (beginnend mit Zeile 0).
Speichern Sie in jedem Knoten die Zeile und die Spalte, in jeder Zeile beginnt die Spalte mit 0. Die zweite Zeile ist also nicht 2,3,4,5,6, sondern 1|0, 1|1, 1|2, 1| 3, 1|4.
Wenn Ihre Suchwurzel 1|1 ist (Zeile 1, zweites Element, in Ihrem netten Baum mit dem Namen "3"), dann haben alle Kinder in Zeile 2
col / 5 = 1
alle Kinder in Reihe 3 haben
col / 25 = 1
und so weiter.
Eine Ebene unter Knoten 2|10 sind Knoten 3|(5*10) bis 3|(5*11-1) =50 .. 55-1
zwei Ebenen darunter sind die Knoten 4|(50*5) bis 4|(55*5-1)
und so weiter.
Schritt 3
Pseudocode:
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
}
Bitte fragen Sie, ob weitere Details benötigt werden.
