m-ary ツリー

グラフ理論において、m分木（非負の整数m）（n分木、k分木、k方向木とも呼ばれる）は、各ノードがm個以下の子を持つ樹状木（または、一部の著者にとっては順序付き木）^{[1] [2]}である。二分木はm = 2の場合の重要なケースであり 、同様に三分木はm = 3の場合のものである。

• 完全なm進木は、各レベル内の各ノードに 0 個またはm 個の子があるm進木です。
• 完全m進木^{[3] [4]}（または、あまり一般的ではないが、完全m進木[ ^5]）は、すべての葉ノードが同じ深さにある完全なm進木である。

• 高さhのm -ary 木の場合、葉の最大数の上限は です。${\displaystyle m^{h}}$
• m進木の高さh にはルート ノードは含まれず、ルート ノードのみを含む木の高さは 0 になります。
• ツリーの高さは、ツリー内の任意のノードの最大深さDに等しくなります。
• 完全m分木におけるノードの総数は であり、高さhは${\displaystyle N}$${\textstyle \sum _{i=0}^{h}m^{i}={\frac {m^{h+1}-1}{m-1}}}$

$${\displaystyle {\begin{aligned}&{\frac {m^{h+1}-1}{m-1}}\geq N>{\frac {m^{h}-1}{m-1}}\\[8pt]&m^{h+1}\geq (m-1)\cdot N+1>m^{h}\\[8pt]&h+1\geq \log _{m}\left((m-1)\cdot N+1\right)>h\\[8pt]&h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil .\end{aligned}}}$$Big-Ωの定義によれば、最大深度は $${\displaystyle D=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m).}$$

• n個のノードを持つ完全なm -ary 木の高さはです。${\textstyle \lfloor \log _{m}((m-1)\cdot n)\rfloor }$
• n個のノードを持つm分木の総数は （カタラン数）である。^[6]${\textstyle C_{n}={\frac {1}{(m-1)n+1}}\cdot {\binom {m\cdot n}{n}}}$

m進木の走査は、二分木の走査と非常によく似ています。前順走査では、親、左サブツリー、右サブツリーの順に走査し、後順走査では、左サブツリー、右サブツリー、親ノードの順に走査します。順序どおりに走査する場合、m > 2ではノードごとに 3 つ以上の子が存在するため、左サブツリーと右サブツリーの概念を定義する必要があります。左/右サブツリーを確立する一般的な方法の 1 つは、子ノードのリストを 2 つのグループに分割することです。ノードの m個の子に順序を定義すると、最初のノードが左サブツリーを構成し、ノードが右サブツリーを構成します。 ${\textstyle \{1,\dots ,\lfloor {\frac {m}{2}}\rfloor \}}$${\textstyle \{\lceil {\frac {m}{2}}\rceil ,\dots ,m\}}$

配列を使用してメリー ツリーを表現するのは非効率的です。実際のアプリケーションでは、ほとんどのノードにm 個未満の子しか含まれていないためです。その結果、メモリ内に未使用の領域が大量に残る疎な配列が生成されます。任意のメリー ツリーをバイナリ ツリーに変換しても、ツリーの高さは定数倍しか増加せず、全体的な最悪のケースの時間計算量には影響しません。つまり、. ${\textstyle O(\log _{m}n)\equiv O(\log _{2}n)}$${\textstyle \log _{2}m\cdot \log _{m}n={\frac {\log m}{\log 2}}\cdot {\frac {\log n}{\log m}}=\log _{2}n}$

まず、特定の親ノードの直下の子ノードをすべてリンクして、リンク リストを作成します。次に、親から最初の (つまり、一番左の) 子へのリンクを保持し、残りの子へのリンクをすべて削除します。すべての内部ノードを処理し、ツリーを時計回りに 45 度回転するまで、すべての子 (子がある場合) に対してこのプロセスを繰り返します。取得されるツリーは、指定されたm進ツリーから取得された目的のバイナリ ツリーです。

m進木は、暗黙的なデータ構造として配列に幅優先順序で格納することもでき、木が完全なm進木である場合、この方法ではスペースが無駄になりません。このコンパクトな配置では、ノードがインデックスi を持つ場合、範囲 {1,…, m } 内のc番目の子はインデックス で見つかり、その親 (存在する場合) はインデックス で見つかります(ルートのインデックスが 0 で、つまり 0 ベースの配列であると仮定)。この方法は、特に順序付けトラバーサル中に、よりコンパクトなストレージと参照の局所性の向上という利点があります。この方法のスペース計算量は です。 ${\displaystyle m\cdot i+c}$${\textstyle \left\lfloor {\frac {i-1}{m}}\right\rfloor }$${\displaystyle O(m^{n})}$

各ノードには、その子ノードへのポインタを格納するための内部配列があります。 ${\displaystyle m}$

配列ベースの実装と比較すると、この実装方法は空間計算量が優れています。 ${\displaystyle O(m\cdot n)}$

考えられるすべてのm進木をリストすることは、仮説や理論を確認する方法として多くの分野で役立ちます。m 進木オブジェクトを適切に表現すると、生成プロセスを大幅に簡素化できます。バイナリ値を使用して特定のインデックスにノードが存在することを示すn 個のノードを持つm進木の深さ優先探索を使用して、ビット シーケンス表現を構築できます。たとえば、ビット シーケンス x=1110000100010001000は、以下に示すように、 n=6 個のノードを持つ 3 進木を表します。

この表現の問題は、すべてのビット文字列を辞書式順に並べると、連続する 2 つの文字列が辞書式で大きく異なる 2 つのツリーを表す可能性があることです。したがって、バイナリ文字列を列挙しても、すべてのm進ツリーが順序どおりに生成されるとは限りません。^[7]より優れた表現は、連続する 1 の間にあるゼロの数を示す整数文字列に基づくもので、単純ゼロ シーケンスと呼ばれます。は、ビット シーケンスに対応する単純ゼロ シーケンスです。ここで、 j は、文字列を適切な長さにするためにシーケンスの末尾に必要なゼロの数です。たとえば、 は、上図の単純ゼロ シーケンス表現です。00433のよりコンパクトな表現は であり、ゼロ シーケンスと呼ばれ、重複する基数が隣接できません。この新しい表現により、 で次の有効なシーケンスを構築できます。単純ゼロ シーケンスは の場合に有効です。 つまり、m進ツリーのビット シーケンス内のゼロの数は、ヌル ポインター (つまり、子ノードが接続されていないポインター) の総数を超えることはできません。この合計は、無効な構造を作成せずに追加する余地があるようにノードに制限を課します(つまり、最後のノードをアタッチするための使用可能な null ポインターを持つ)。 ${\textstyle S=s_{1},s_{2},\dots ,s_{n-1}}$${\textstyle 10^{s_{1}}10^{s_{2}}\ldots 10^{s_{n-1}}10^{j}}$${\displaystyle 1110000100010001000\equiv 10^{0}10^{0}10^{4}10^{4}10^{3}\equiv 00433}$${\displaystyle 0^{2}4^{1}3^{2}}$${\displaystyle O(1)}$$${\displaystyle \sum _{i=1}^{i=j}s_{i}\leq (m-1)j\qquad \forall j\leq n-1.}$$${\displaystyle n-1}$${\displaystyle n^{t}h}$

以下の表は、4 つのノードを持つすべての3進木のすべての有効な単純ゼロ シーケンスのリストを示しています。

表の右下 (つまり「000」) から始まるバックボーン テンプレートは、「000」から「006」までの可能な順序付きツリーの生成を制御します。このグループ (「00X」) のバックボーン テンプレートは下図のとおりで、「x」のラベルの付いた位置にノードが追加されています。

バックボーン テンプレートのすべての可能な位置を使い果たすと、以下に示すように 3 番目のノードを 1 つ右にシフトして新しいテンプレートが構築され、「X」というラベルの付いたすべての可能な位置を使い果たすまで同じ列挙が行われます。

すべてのm進木の列挙表 (および )に戻ると、 "006" から "010" への見かけ上のジャンプは、以下に示すようにアルゴリズム的に簡単に説明できることが容易にわかります。 ${\displaystyle m=3}$${\displaystyle n=4}$

この列挙の擬似コードは以下の通りである: ^[7]

手順NEXT( s 1 , s 2 , …, s n −1 )
    すべてのiに対してs i = 0の場合  
        終了した
    そうでない場合
        i ← max { i | s i > 0}
         s i ← s i − 1
         i < n − 1の場合s  i ← ( i + 1) ⋅ ( m − 1) − sum( s j )
        終了j ← i + 2, i + 3, …, n − 1 の
            場合s j ← k − 1
    終了終了
            
         

最悪時間がかかる生成アルゴリズムは、時間の計算量にループや再帰が含まれないため、ループレスと呼ばれます。メリーランド ツリーのループレス列挙は、初期化後に に連続するツリー オブジェクトを生成する場合、ループレスであると言われます。 がそのノードの 1 つで、その番目の子であるメリーランド ツリーT が与えられると、での左 t 回転は、 をルート ノード にして、 とそのすべてのサブツリーを の子にすることで実行されます。さらに、 の左端の子を に割り当て、 の右端の子はがルートに昇格している間、 に接続されたままになります。以下に示すように: ${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle a}$${\displaystyle d}$${\displaystyle t}$${\displaystyle a}$${\displaystyle d}$${\displaystyle b}$${\displaystyle a}$${\displaystyle m-1}$${\displaystyle d}$${\displaystyle a}$${\displaystyle d}$${\displaystyle d}$

m-ary ツリーを左ツリーに変換します
    。i = 1... nの場合 :
          t = 2... mの場合:
              tが深さi ≠ 1のノードの子である場合:  深さi
              
                のノードでの Lt 回転end while 
          end for 
     end for

dでの右 t 回転は、この操作の逆です。Tの左チェーンは、 がルートであり、 を除くすべてのノードが最も左の (つまり、) ポインタに接続された 1 つの子を持つノードのシーケンスです。任意のm進木は、 2からmまでのtの有限左 t 回転のシーケンスを使用して、左チェーン木に変換できます。具体的には、各ノードで左 t 回転を実行して、各深さでそのサブツリーがすべてnullになるまで実行できます。次に、 で表される深さiで実行された左 t 回転の数のシーケンスは、同じ右 t 回転のシーケンスを実行することで復元できる m 進木 のコードワードを定義します。${\displaystyle x_{1},x_{2},\dots ,x_{n}}$${\displaystyle x_{1}}$${\displaystyle x_{n}}$${\displaystyle m[1]}$${\displaystyle x_{i}}$${\displaystyle m-1}$${\displaystyle c_{i}}$

のタプルがルート（つまり、i =1）で発生したL-2回転、L-3回転、...、Lm回転の数を表すものとします。この場合、 は深さiで必要なLt回転の数です。 ${\displaystyle m-1}$${\displaystyle c_{1},c_{2},\dots ,c_{m-1}}$${\displaystyle c_{(i-1)(m-1)+t-1}}$

各深さにおける左回転の回数を記録することは、 m進木をエンコードする方法である。したがって、すべての可能な合法的なエンコードを列挙することは、与えられたmとnに対するすべてのm進木を生成するのに役立つ。しかし、 m個の非負整数のシーケンスのすべてが有効なm進木を表すわけではない。非負整数のシーケンスがm進木の有効な表現となるのは、 ^[8]の場合のみである。${\displaystyle c_{i}}$${\displaystyle (n-1)\cdot (m-1)+1}$ $${\displaystyle \sum _{i=j}^{n}\sum _{t=2}^{m}c_{(i-1)(m-1)+t-1}\qquad \leq n-j,\qquad \forall j\in 0\dots n.}$$

n個のノードを持つm 進法の辞書式最小のコードワード表現はすべてゼロであり、最大のものはn −1 個の 1 の後にその右側に m −1 個のゼロが続くものです。

1からn⋅ ( k −1)
    までのすべてのiに対してc[i]をゼロに初期化する
    p[i]をn − 1に設定する。iは1からnまで、
     sum ← 0、
     j ← m − 1

終了条件
    c[1] = n − 1のとき終了する

手順NEXT [8] 
    sum ← sum + 1 − c [ j + 1]
     c [j] ← c [ j ] + 1
     if  p [ q [ j ]] > p [ q [ j + 1]] + 1 then 
        p [ q [ j ]] ← p [ q [ j + 1]] + 1
     end if 
    p [ q [ j + c [ j ]]] ← p [ q [ j ]]
     c [ j + 1] ← 0
     if  sum = p [ q [ j ]] then 
        j ← j − 1
     else 
        p [ n ] ← sum 
        j ← m − 1
     end if 
end

m進木の応用の 1 つは、受け入れ可能な文字列の検証用の辞書を作成することです。そのためには、m を有効なアルファベットの数 (たとえば、英語のアルファベットの文字数) と等しくし、ツリーのルートを開始点とします。同様に、各子は、文字列内の次の可能な文字を表す最大m個の子を持つことができます。したがって、パスに沿った文字は、キーの終了文字を「ターミナル ノード」としてマークすることにより、有効なキーを表すことができます。たとえば、以下の例では、「at」と「and」は有効なキー文字列であり、「t」と「d」はターミナル ノードとしてマークされています。ターミナル ノードには、特定のキーに関連付ける追加情報を格納できます。Bツリー、オクツリー、トライを使用してこのような辞書を作成する同様の方法があります。

• 分岐因子
• 左子右兄弟二分木
• 二分木

• Storer, James A. (2001)。『データ構造とアルゴリズム入門』。ボストン・ビルクハウザー社。ISBN 3-7643-4253-6。

• N 分木、Bruno R. Preiss、Ph.D、P.Eng