幅優先探索方式での一般的なツリートラバーサル（無限）

私はまだ考えていますが、ツリーをトラバースするよりもはるかに高速で、すべての可能な位置のposition_idになります。特定のレベルの完全なツリーを見ると、私が何を意味しているのかがわかります。例はそのように見えます。

positionとposition_idの間の接続は、単純なint演算（divとモジュロ）を使用したものです。

サブツリー内のすべてのノードは、これらのプロパティの一部を共有します。たとえば、ノード4の直接のサブノード（2行目の3番目のノード）は数字です

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番目の行は2、3、4、5、6ではなく、1 | 0、1 | 1、1 | 2、1|です。 3、1|4。

検索ルートが1|1（行1、2番目の要素、「3」という名前の素敵なツリー）の場合、行2のすべての子は

  col / 5 = 1

3行目のすべての子供が持っています

  col / 25 = 1

など。

ノード2|10の1つ下のレベルは、ノード3 |（5 * 10）から3 |（5 * 11-1）=50 .. 55-1

下の2つのレベルは、ノード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
}

詳細が必要かどうかお尋ねください。