Allmän trädgenomgång (oändlig) i bredd-först söksätt

Jag tänker fortfarande, men mycket snabbare än att korsa trädet skulle vara en position_id för varje möjlig position. Om du tittar på ett komplett träd på en viss nivå skulle du se vad jag menar - ditt exempel ser ut så.

Kopplingarna mellan position och position_id är något med enkel int-aritmetik (div och modulo).

Alla noder i ett underträd delar några av dessa egenskaper - till exempel är de direkta subnoderna för nod 4 (tredje noden i andra raden) nummer

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

Så du skulle fortfarande behöva passera nivåerna i en loop, men inte noderna om du hanterar det positionsnumret i varje nod.

Steg 2:

Rad r har 5^r element (börjar med rad 0).

Lagra i varje nod raden och kolumnen, i varje rad börjar kolumnen med 0. Så den andra raden är inte 2,3,4,5,6 utan är 1|0, 1|1, 1|2, 1| 3, 1|4.

Om din sökrot är 1|1 (rad 1, andra element, i ditt fina träd som heter "3"), så har alla barn i rad 2

  col / 5 = 1

alla barn på rad 3 har

  col / 25 = 1

och så vidare.

En nivå under nod 2|10 är noderna 3|(5*10) till 3|(5*11-1) =50 .. 55-1

två nivåer nedanför är noderna 4|(50*5) till 4|(55*5-1)

och så vidare.

Steg 3

Pseudokod:

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
}

Fråga om mer information behövs.