万年木

M-ary_tree
グラフ理論では、m 分木( n分木、k分木、またはk方向木とも呼ばれます) は、各ノードがm 個以下の子を持つ根付き木です。二分木はm = 2の特殊なケースで 、三分木はm = 3 で子を 3 つに制限する別のケースです。
m=5の m-ary ツリーの例

コンテンツ
1 多分木の種類
2 多分木の性質
3 マリーツリーのトラバーサル メソッド
4 m分木を二分木に変換する
5 多分木を格納する方法
5.1 配列 5.2 ポインターベース
6 マリーツリーの列挙
6.1 ループレス列挙
7 応用
8 こちらもご覧ください
9 参考文献
10 外部リンク

多分木の種類
完全なm分木は、各レベル内ですべてのノードが 0 個またはm 個の子を持つm 分木です。
完全な多分木は、スペース効率が最大の多分木です。最後のレベルを除くすべてのレベルで完全に満たされている必要がただし、最後のレベルが完了していない場合は、ツリーのすべてのノードを「できるだけ左に」配置する必要が
完全なm分木は、すべてのリーフ ノードが同じ深さにある完全な m 分木です。

多分木の性質
高さhのm 分木の場合、葉の最大数の上限は次のとおりです。
メートル
時間
{ m^{h}}
. m 分木の高さhにはルート ノードは含まれず、ルート ノードのみを含むツリーの高さは 0 です。
ツリーの高さは、ツリー内の任意のノードの最大深さDに等しくなります。
ノードの総数 N { N}

完全な多元木では = 0
時間
メートルI =
メートル
時間+ 1 − 1
メートル− 1
{textstyle sum _{i=0}^{h}m^{i}={frac {m^{h+1}-1}{m-1}}}

、高さhは
メートル間 + 1 − 1
メートル− 1 ≥
N > メートル間 − 1
メートル− 1
メートル
時間+ 1 ≥( メートル − 1) ⋅
N+ 1 >
メートル
時間
時間+ 1 ≥ グ
メートル( ( メートル− 1 ) ⋅ N + 1 ) >
時間
時間 ≥ ⌈
ログ
メートル( ( メートル− 1 ) ⋅ N + 1 ) − −0 −1 −2
{ {begin{aligned}&{frac {m^{h+1}-1}{m-1}}geq N>{frac {m^{h}-1}{m-1 }}\&m^{h+1}geq (m-1)cdot N+1>m^{h}\&h+1geq log _{m}left ((m-1)cdot N+1right)>h\&hgeq leftlceil log_{m}((m-1)cdot N+1)-1right rceil .end{aligned}}}
{frac {m^{h}-1}{m-1}}\&m^{h+1}geq (m-1)cdot N+1>m^{h}\&h+1geq log _{m}left((m-1)cdot N+1right)>h\&hgeq leftlceil log _{m}((m-1)cdot N+1)-1rightrceil .end{aligned}}}””>
Big-Ωの定義により、最大深さD =
時間≥ ⌈
ログ
メートル( ( メートル− 1 ) ⋅ N + 1 ) − −0 −1= 〇 ( ログ
メートルn ) = 〇( ログn / グ
メートル ) { D=hgeq leftlceil log _{m}((m-1)cdot N+1)-1rightrceil =O(log _{m}n)=O( log n/log m)}

n 個のノードを持つ完全なm 分木の高さは、 ⌊ ログ
メートル( ( メートル− 1 ) ⋅ n ) ⌋
{textstyle lfloor log _{m}((m-1)cdot n)rfloor }
. n 個のノードを持つ可能なm 分木の総数は、次のとおりです。
Cn = 1( メートル− 1 ) n + 1 ⋅( メートル ⋅ n n) {textstyle C_{n}={frac {1}{(m-1)n+1}}cdot {binom {mcdot n}{n}}}
(これはカタロニア語の数字です)。

マリーツリーのトラバーサル メソッド
主な記事:
ツリー トラバーサル
多分木の走査は、二分木の走査と非常によく似ています。前順トラバーサルは、親、左サブツリー、および右サブツリーに進み、後順トラバーサルでは、左サブツリー、右サブツリー、および親ノードに進みます。m > 2の場合、ノードごとに 2 つ以上の子があるため、順序どおりにトラバースするには、左と右のサブツリーの概念を定義する必要が左右のサブツリーを確立する一般的な方法の 1 つは、子ノードのリストを 2 つのグループに分割することです。ノードのm 個の子に順序を定義することにより、最初の { 1 … ⌊
メートル2 } {textstyle {1，dots ，lfloor {frac {m}{2}}rfloor }}

ノードは左サブツリーを構成し、{ ⌈
メートル 2 ⌉ … メートル } {textstyle {lceil {frac {m}{2}}rceil ，dots ，m}}

ノードは右のサブツリーを構成します。

m分木を二分木に変換する

多分木から二分木への変換例。 m=6 実際のアプリケーションでは、ほとんどのノードにm未満の子が含まれているため、mary ツリーを表すために配列を使用するのは効率的ではありません。結果として、この事実は、メモリ内に大きな未使用スペースを持つまばらな配列につながります。任意のmaryツリーをバイナリ ツリーに変換しても、ツリーの高さが一定の係数だけ増加するだけで、全体的な最悪の場合の時間計算量には影響しません。言い換えると、 〇 ( ログ
メートルn ) ≡ 〇( ログ2 n )
{textstyle O(log _{m}n)equiv O(log _{2}n)}

以来
ログ 2 メートル ⋅ ログ
メートルn =
ログ
メートル
ログ2 ⋅
ログ n ログ
メートル = ログ2 n
{textstyle log _{2}mcdot log _{m}n={frac {log m}{log 2}}cdot {frac {log n}{log m}} =ログ _{2}n}
. まず、リンク リストを形成するために、特定の親ノードの直接の子ノードをすべてリンクします。次に、親から最初の (つまり、一番左の) 子へのリンクを保持し、残りの子への他のすべてのリンクを削除します。すべての内部ノードを処理し、ツリーを時計回りに 45 度回転させるまで、すべての子 (子がいる場合) に対してこのプロセスを繰り返します。得られる木は、与えられたm分木から得られる目的の二分木です。
多分木を格納する方法編集

配列

m=3のm分木を
配列
に格納する例
m 分木は、配列内の暗黙的なデータ構造として幅優先の順序で格納することもできます。木が完全なm 分木である場合、この方法はスペースを無駄にしません。このコンパクトな配置では、ノードにインデックスiがある場合、範囲 {1，…， m }内のそのc番目の子がインデックスで見つかります
メートル⋅ I + c
{ mcdot i+c}

、その親 (存在する場合) はインデックスで見つかります
⌊I − 1 メートル ⌋ {textstyle leftlfloor {frac {i-1}{m}}rightrfloor }
(ルートのインデックスが 0、つまり 0 ベースの配列であると仮定します)。この方法は、特に事前注文トラバーサル中に、よりコンパクトなストレージと参照の局所性が向上するという利点がこのメソッドの空間複雑度は 〇 ( メートル n) { O(m^{n})}

.

ポインターベース
各ノードには、その各ノードへのポインターを格納するための内部配列が
メートル
{ m}

子供：

m = 4
の場合の m-ary ツリーのポインターベースの実装 配列ベースの実装と比較して、この実装方法は、次のスペースの複雑性に優れています。 〇 ( メートル⋅ n )
{ O(mcdot n)}

.

マリーツリーの列挙
主な記事:
列挙的組み合わせ論
すべての可能性のあるm 分木をリストすることは、仮説や理論を確認する方法として、多くの分野で役立ちます。マリーツリー オブジェクトを適切に表現することで、生成プロセスを大幅に簡素化できます。バイナリ値を使用して特定のインデックスでノードの存在を示すn 個のノードを持つmツリーの深さ優先検索を使用して、ビット シーケンス表現を構築できます。たとえば、ビット シーケンスx=1110000100010001000は、以下に示すように、 n=6ノードの 3 分木を表しています。

この表現の問題点は、すべてのビット文字列を辞書順でリストすると、2 つの連続する文字列が辞書順で大きく異なる 2 つのツリーを表す可能性があることです。したがって、バイナリ文字列の列挙は、必ずしもすべてのmaryツリーの順序付けされた生成をもたらすとは限りません。より適切な表現は、単純なゼロ シーケンスとして知られる、連続するゼロの間のゼロの数を示す整数文字列に基づいています。S = s 1 s
2 … sn − 1 {textstyle S=s_{1}，s_{2}，dots ，s_{n-1}}

ビットシーケンスに対応する単純なゼロシーケンスです10 s 0 s
2… 10 s n −1 0 j {textstyle 10^{s_{1}}10^{s_{2}}ldots 10^{s_{n-1}}10^{j}}

ここで、jは、文字列を適切な長さにするためにシーケンスの末尾に必要なゼロの数です。例えば、 1110000100010001000 ≡10 0 10 0 10 4 10 4 10 100 101 102
{ 1110000100010001000equiv 10^{0}10^{0}10^{4}10^{4}10^{3}equiv 00433}

は、上の図の単純なゼロ シーケンス表現です。00433のよりコンパクトな表現は0 2 4 1 3 2
{ 0^{2}4^{1}3^{2}}

、これはゼロ配列と呼ばれ、重複する塩基が隣接することはできません。この新しい表現により、次の有効なシーケンスを構築できます 〇 ( 1 ) { O(1)}

. 次の場合、単純なゼロ シーケンスが有効です。∑ I=1 = j s I ≤( メートル− 1 ) j ∀ j ≤ n − −0
{ sum _{i=1}^{i=j}s_{i}leq (m-1)jqquad forall jleq n-1.}

つまり、
m 分木のビット シーケンス内のゼロの数は、ヌル ポインター (つまり、子ノードが接続されていないポインター) の総数を超えることはできません。この合計は制限を加えていますn − 1
{ n-1}

ノードを追加する余地があるようにn t
時間
{ n^{t}h}

無効な構造を作成せずに (つまり、最後のノードをアタッチするためのヌル ポインターを使用できるようにします)。
以下の表は、4 つのノードを持つすべての3 分木のすべての有効な単純なゼロ シーケンスのリストを示しています。222 200 111 033 013 221 132 110 032 2220 2221 2222 2223
031011 213 130 104 030 010 212 123 103 0110 0111 0112 0113
102023 005 210 121 101 022 004 204 120 0230 0231 0232 0233
114042 020 002 202 113 041 015 001 201 0420 0421 0422 0423
テーブルの右下 (つまり、「000」)から開始して、「000」から「006」までの可能な順序付きツリーの生成を管理するバックボーン テンプレートがこのグループ (「00X」) のバックボーン テンプレートを以下に示します。ここでは、「x」とラベル付けされた位置にノードが追加されています。

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

すべての mツリーの列挙の表に戻ります。ここで、
メートル= 3
{ m=3}
と n = 4
{ n=4}

、「006」から「010」への明らかなジャンプを簡単に観察できます。これは、以下に示すように、アルゴリズム的な方法で自明に説明できます。

この列挙の疑似コードは以下のとおりです:
プロシージャNEXT( s 1 ， s 2 ， …， s n −1 ) if s i = 0 for all i then
終了した さもなければ
i max { i | s i > 0}
s i s i − 1
if i < n − 1 then
s i ( i + 1) ⋅ ( m − 1) − sum( s j ) end if for j i + 2， i + 3， …， n − 1
s j k − 1 end if end

ループレス列挙
を取る生成アルゴリズム 〇 ( 1 ) { O(1)}

 時間の複雑さにループや再帰を含めることができないため、最悪の場合の時間はループレスと呼ばれます。マリー ツリーのループレス列挙は、初期化後に連続するツリー オブジェクトを生成する場合、ループレスであると言われます。 〇 ( 1 ) { O(1)}

 . 与えられたm-ツリーTに対して、 a { a}

 そのノードの 1 つであり、 d { d}

  t
{ t}

 – 番目の子、左から t の回転 a { a}

 作ることによって行われます d { d}

 ルートノード、および作成 b { b}

 およびその子であるすべてのサブツリー a { a}

 、さらに、
メートル− 1
{ m-1}

 のほとんどの子供を残しました d { d}

 に a { a}

 の右端の子 d { d}

 その間、それに付着したままです d { d}

 以下に示すように、ルートに昇格します。

  m 分木を左木に変換 for i = 1… n :
for t = 2… m : while t child of node at depth i ≠ 1:
深さiのノードでの Lt 回転 end whileend for nd for
dでの右 t 回転は、この操作の逆です。Tの左鎖は、X 1 X 2 … X n { x_{1}，x_{2}，dots ，x_{n}}

 そのようなノードX 1 { x_{1}}

 ルートおよびそれ以外のすべてのノードX n { x_{n}}

 1 つの子を左端に接続します (つまり、
メートル
{ m}

 ) ポインター。任意のm分木は、 2からmまでのtに対する一連の有限な left-t 回転を使用して、左鎖木に変換できます。具体的には、これは各ノードで left-t ローテーションを実行することで実行できます。X I { x_{i}}

 そのすべてまで
メートル− 1
{ m-1}

 サブツリーは各深さでnullになります。次に、深さiで実行される left-t 回転の数のシーケンスは、c I
{ c_{i}}

 同じシーケンスの右 t 回転を実行することによって復元できる mary ツリーのコードワードを定義します。
しましょう
メートル− 1
{ m-1}

 のタプルc 1 c
2 … c
メートル − 1
{ c_{1}，c_{2}，dots ，c_{m-1}}

 は、ルートで発生したL-2回転、L-3回転、…、Lm回転の数を表します(つまり、i =1)。次に、 c ( I − 1 ) ( メートル − 1) + t − 1 { c_{(i-1)(m-1)+t-1}}

 深さiで必要なLt回転数です。
各深さで左回転のカウントを取得することは、 m 分木をエンコードする方法です。したがって、可能なすべての合法的なエンコーディングを列挙すると、特定の mおよびnのすべてのm – ary ツリーを生成するのに役立ちます。すべてではありませんc I
{ c_{i}}

 m 個の負でない整数のシーケンスは、有効な m-ary ツリーを表します。のシーケンス( n− 1 ) ⋅( メートル− 1 ) + 1
{ (n-1)cdot (m-1)+1}

 の場合に限り、負でない整数は mary ツリーの有効な表現です。∑ I = j
n∑ t = 2
メートル c ( I− 1 )( メートル− 1 ) + t − 1 ≤ n −0
j ∀j ε 0 … n .
{ sum _{i=j}^{n}sum _{t=2}^{m}c_{(i-1)(m-1)+t-1}qquad leq nj， qquad forall jin 0dots n.}

n 個のノードを持つm-aryの辞書編集的に最小のコードワード表現はすべてゼロであり、最大のものはn -1 の 1 であり、その右側にm -1 のゼロが続きます。 1 からnまでのすべての i に対して c をゼロに初期化⋅( k − 1) p 1 から n までの i に対してn − 1 に 設定sum 0 j m − 1終了条件 c = n − 1で終了手順NEXT sum sum + 1 − c c c + 1 if p + 1 then
p + 1 pの場合終了 c 合計の場合0 = p [ q ] then j j − 1 else p sum j m − 1 end if end

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

 

こちらもご覧ください
分岐係数
左子右兄弟二分木
二分木

参考文献
^ 「順序付けられた木」. 2012年 11 月 19 日閲覧。
^ ブラック、ポール E. （2011 年 4 月 20 日)。「完璧なk-aryツリー」 . 米国国立標準技術研究所。2011年10 月 10 日閲覧。
^ グラハム、ロナルド L.; クヌース、ドナルド E.; パタシニク、オレン (1994)。Concrete Mathematics: A Foundation for Computer Science (第 2 版) . AIP。
^ Baronaigien、Dominique Roelants van （2000)。「K-ary ツリーのループ フリー生成」。アルゴリズムのジャーナル。35 (1): 100–107. ドイ: 10.1006/jagm.1999.1073 .
^ コーシュ、ジェームズF（1994）。「k-ary ツリー シーケンスのループレス生成」。情報処理の手紙。エルゼビア。52 (5): 243–247. ドイ：10.1016/0020-0190(94)00149-9 .
Storer、ジェームズ A. （2001)。データ構造とアルゴリズムの紹介。ビルクホイザー ボストン。ISBN 3-7643-4253-6.

外部リンク
N分木、Bruno R. Preiss、Ph.D、P.Eng.”