Lintasan pohon umum (tak terbatas) dengan cara pencarian luas-pertama

Saya masih berpikir, tetapi jauh lebih cepat daripada melintasi pohon akan menjadi position_id untuk setiap posisi yang mungkin. Jika Anda melihat pohon lengkap dari tingkat tertentu, Anda akan melihat apa yang saya maksud - contoh Anda terlihat seperti itu.

Hubungan antara position dan position_id adalah sesuatu dengan aritmatika int sederhana (div dan modulo).

Semua node dalam subpohon berbagi beberapa properti tersebut - misalnya subnode langsung dari node 4 (simpul ketiga di baris kedua) adalah angka

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

Jadi Anda masih harus melintasi level dalam satu lingkaran, tetapi bukan node jika Anda mengelola nomor posisi itu di setiap node.

Langkah 2:

Baris r memiliki 5^r elemen (dimulai dengan baris 0).

Simpan di setiap node baris dan kolom, di setiap baris kolom dimulai dengan 0. Jadi baris kedua bukan 2,3,4,5,6 tetapi 1|0, 1|1, 1|2, 1| 3, 1|4.

Jika akar pencarian Anda adalah 1|1 (baris 1, elemen kedua, di pohon bagus Anda bernama "3"), maka semua anak di baris 2 memiliki

  col / 5 = 1

semua anak di baris 3 memiliki

  col / 25 = 1

dan seterusnya.

Satu tingkat di bawah simpul 2|10 adalah simpul 3|(5*10) til 3|(5*11-1) =50 .. 55-1

dua level di bawahnya adalah node 4|(50*5) hingga 4|(55*5-1)

dan seterusnya.

Langkah 3

Kode semu:

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
}

Silakan tanyakan jika diperlukan lebih banyak detail.