Algemene boomtraversal (oneindig) in de breedte-first zoekmanier

Ik denk nog steeds na, maar veel sneller dan het doorkruisen van de boom zou een position_id zijn voor elke mogelijke positie. Als je naar een volledige boom van een bepaald niveau kijkt, zou je zien wat ik bedoel - je voorbeeld ziet er zo uit.

De verbindingen tussen position en position_id zijn iets met eenvoudige int-rekenkunde (div en modulo).

Alle knooppunten in een substructuur delen enkele van die eigenschappen - bijvoorbeeld de directe subknooppunten van knooppunt 4 (derde knooppunt in de tweede rij) zijn nummers

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

Je zou dus nog steeds de niveaus in een lus moeten doorlopen, maar niet de knooppunten als je dat positienummer in elk knooppunt beheert.

Stap 2:

Rij r heeft 5^r elementen (beginnend met rij 0).

Bewaar in elk knooppunt de rij en de kolom, in elke rij begint de kolom met 0. De tweede rij is dus niet 2,3,4,5,6 maar is 1|0, 1|1, 1|2, 1| 3, 1|4.

Als je zoekwortel 1|1 is (rij 1, tweede element, in je mooie boom met de naam "3"), dan hebben alle kinderen in rij 2

  col / 5 = 1

alle kinderen in rij 3 hebben

  col / 25 = 1

enzovoort.

Een niveau onder knooppunt 2|10 zijn knooppunten 3|(5*10) til 3|(5*11-1) =50 .. 55-1

twee niveaus eronder zijn knooppunten 4|(50*5) til 4|(55*5-1)

enzovoort.

Stap 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
}

Vraag of er meer details nodig zijn.