Все още мисля, но много по-бързо от преминаването по дървото би било position_id за всяка възможна позиция. Ако погледнете цялостно дърво от определено ниво, ще видите какво имам предвид - примерът ви изглежда така.
Връзките между позиция и position_id са нещо с проста int аритметика (div и modulo).
Всички възли в поддървета споделят някои от тези свойства - например директните подвъзли на възел 4 (трети възел във втория ред) са числа
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
Така че все пак ще трябва да преминете нивата в цикъл, но не и възлите, ако управлявате този номер на позиция във всеки възел.
Стъпка 2:
Ред r има 5^r елемента (започвайки с ред 0).
Съхранявайте във всеки възел реда и колоната, във всеки ред колоната започва с 0. Значи вторият ред не е 2,3,4,5,6, а е 1|0, 1|1, 1|2, 1| 3, 1|4.
Ако вашият корен за търсене е 1|1 (ред 1, втори елемент, във вашето хубаво дърво с име "3"), тогава всички деца в ред 2 имат
col / 5 = 1
всички деца в ред 3 имат
col / 25 = 1
и така нататък.
Едно ниво под възел 2|10 са възли 3|(5*10) до 3|(5*11-1) =50 .. 55-1
две нива по-долу са възли 4|(50*5) до 4|(55*5-1)
и така нататък.
Стъпка 3
Псевдокод:
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
}
Моля, попитайте дали са необходими повече подробности.
