Obecné procházení stromu (nekonečno) způsobem prohledávání do šířky

Stále přemýšlím, ale mnohem rychlejší než procházení stromu by bylo position_id pro každou možnou pozici. Pokud se podíváte na úplný strom určité úrovně, uvidíte, co tím myslím – váš příklad vypadá takto.

Spojení mezi pozicí a position_id je něco s jednoduchou aritmetikou int (div a modulo).

Všechny uzly v podstromech sdílejí některé z těchto vlastností – například přímé poduzly uzlu 4 (třetí uzel ve druhém řádku) jsou čísla

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

Stále byste tedy museli procházet úrovněmi ve smyčce, ale ne uzly, pokud spravujete toto číslo pozice v každém uzlu.

Krok 2:

Řádek r má 5^r prvků (počínaje řádkem 0).

Uložte do každého uzlu řádek a sloupec, v každém řádku sloupec začíná 0. Druhý řádek tedy není 2,3,4,5,6, ale je 1|0, 1|1, 1|2, 1| 3, 1|4.

Pokud je váš kořen vyhledávání 1|1 (řádek 1, druhý prvek, ve vašem pěkném stromu s názvem „3“), pak všechny děti v řádku 2 mají

  col / 5 = 1

všechny děti v řadě 3 mají

  col / 25 = 1

a tak dále.

Jednu úroveň pod uzlem 2|10 jsou uzly 3|(5*10) až 3|(5*11-1) =50 .. 55-1

dvě úrovně níže jsou uzly 4|(50*5) až 4|(55*5-1)

a tak dále.

Krok 3

Pseudokód:

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
}

Zeptejte se, zda jsou potřeba další podrobnosti.