二分木

コンピュータサイエンスにおいて、二分木は各ノードが最大で2つの子（左の子と右の子と呼ばれる）を持つ木構造のデータである。つまり、k = 2のk分木である。集合論を用いた再帰的な定義では、二分木は組（ L 、 S 、 R ）であり、LとRは二分木または空集合であり、Sはルートを含む単一集合である。 ^{[1] [2]}

グラフ理論の観点から見ると、ここで定義される二分木は樹枝状構造である。^{[3]したがって、二分木は}分岐樹枝状構造とも呼ばれる。^[3]この用語は、現代のコンピュータサイエンスの用語が普及する前の初期のプログラミング書籍^[4]に登場している。二分木を有向グラフではなく無向グラフとして解釈することも可能であり、その場合、二分木は順序付けられた根付き木である。^[5]木が根付きであることを強調するために、一部の著者は二分木ではなく根付き二分木を使用するが、上で定義されているように、二分木は常に根付きである。^[6]

数学において、二分木と呼ばれるものは、著者によって大きく異なります。コンピュータサイエンスで一般的に使用される定義を使用する人もいますが^[7]、葉以外のすべての木がちょうど2つの子を持つものと定義し、必ずしも子を左と右に分類しない人もいます^{[8] 。}

コンピューティングでは、バイナリ ツリーは次の 2 つの非常に異なる方法で使用できます。

• まず、各ノードに関連付けられた何らかの値またはラベルに基づいてノードにアクセスする手段として。^[9]このようにラベル付けされた二分木は、二分探索木と二分ヒープの実装に使用され、効率的な検索とソートのために使用されます。ルート以外のノードを、子ノードが 1 つしかない場合でも左の子または右の子として指定することは、これらのアプリケーションの一部で重要であり、特に二分探索木では重要です。^[10]ただし、特定のノードをツリーに配置することは、概念情報の一部ではありません。たとえば、通常の二分探索木では、ノードの配置は、ノードが追加された順序にほぼ完全に依存し、意味を変えずに再配置できます (たとえば、 のバランスをとることによって)。
• 2 番目は、関連する分岐構造を持つデータの表現としてです。このような場合、他のノードの下や左または右にあるノードの特定の配置は情報の一部です (つまり、それを変更すると意味が変わります)。一般的な例としては、ハフマン コーディングとクラドグラムがあります。日常的に文書を章、セクション、段落などに分割することは、バイナリ ツリーではなくn 元ツリーの類似した例です。

二分木を定義するには、子の1つだけが空である可能性を認めなければならない。そのためには、いくつかの教科書では拡張二分木と呼ばれるアーティファクトが必要である。拡張二分木は再帰的に次のように定義される: ^[11]

• 空集合は拡張二分木である
• T ₁と T 2_が拡張二分木である場合、これらの部分木が空でない場合、エッジを追加することによって、T 1 の左側と T 2 の右側に接続されたルート r を追加することによって得られる拡張二分木を_{T 1 •} T 2 で表します[ _' ^{T 1 • T 2 ' 記号の 'r' はどこに行ったの_か説明_が必要です]}。

この構成を想像する（そして用語を理解する）別の方法は、空集合の代わりに異なるタイプのノード（例えば通常のノードが円であれば四角形のノード）を考えることです。^[12]

二分木は根付き木であり、順序付き木（別名平面木）でもあり、各ノードは最大で 2 つの子を持ちます。根付き木は自然にレベルの概念（根からの距離）を伝えます。したがって、すべてのノードに対して、子の概念は、そのノードに 1 レベル下に接続されているノードとして定義できます。これらの子の順序付け（たとえば、平面上に描画するなど）により、左の子と右の子を区別できます。^[13]しかし、これでは、左の子はあるが右の子がないノードと、右の子はあるが左の子がないノードを区別することはできません。

必要な区別は、まず辺を分割することによって行うことができます。つまり、バイナリ ツリーをトリプレット (V, E ₁ , E ₂ ) として定義します。ここで、(V, E ₁ ∪ E ₂ ) は根付きツリー (樹状) であり、E ₁ ∩ E _{2 は}空であり、また、すべてのj ∈ { 1, 2 } に対して、すべてのノードが最大で 1 つの E _j子を持つことを要求します。^[14]区別を行うより非公式な方法は、数学百科事典を引用して、「すべてのノードには左の子、右の子、どちらもない、または両方がある」と言い、これらが「すべて異なる」バイナリ ツリーであると指定することです。^[7]

樹木に関する用語は十分に標準化されていないため、文献によって用語が異なります。

• あ根付き二分木にはルートノードがあり、各ノードには最大 2 つの子があります。

• あ完全二分木（適切な、^[15] 平面、または厳密な二分木と呼ばれることもある^[16][17]は、すべてのノードが0または2個の子を持つ木である。完全二分木を定義する別の方法は、再帰定義。完全二分木は次のいずれかである:^[11]
  • 単一の頂点 (ルート ノードとしての単一のノード)。
  • ルート ノードに 2 つのサブツリーがあり、両方とも完全なバイナリ ツリーであるツリー。
• あ完全二分木とは、すべての内部ノードが2つの子を持ち、すべての葉が同じ深さまたは同じレベル（ルートノードからノードまでのエッジまたはリンクの数として定義されるノードのレベル）を持つ二分木です。^[18]完全二分木は完全な二分木です。
• あ完全二分木は、最後のレベルを除くすべてのレベルが完全に埋められており、最後のレベルのすべてのノードが可能な限り左に配置されている最終レベルh^{には 1 ～ 2 個のh}ノードが存在する可能性があります。^[19]したがって、完全な木は常に完全ですが、完全な木は常に完全であるとは限りません。一部の著者は、完全なを指すために完全という、その場合、このタイプの木（最後のレベルが埋められていない可能性があります）をほぼ完全な二分木またはほぼ完全な二分木と呼びます。^[20][21]完全な二分木は、配列を使用して効率的に表現できます。^[19]

• 無限完全二分木はレベルを持つ木で、各レベルdについて、レベル d に存在するノードの数は 2 ^dに等しくなります。すべてのレベルの集合の基数は(可算無限) です。すべてのパス (いわゆる「葉」) の集合の基数は不可算であり、連続体の基数を持ちます。${\displaystyle {\aleph _{0}}}$${\displaystyle {\aleph _{0}}}$
• バランスのとれた二分木とは、各ノードの左と右のサブツリーの高さ（サブツリーの最上位ノードから最遠のノードまでの辺の数）の差が1以下（または歪度が1以下）である二分木構造である。^[22]また、どの葉もルートから他の葉よりも遠く離れていない二分木を考えることもできる。（異なるバランス方式では、「遠く離れている」の定義が異なります。^[23]）
• 退化した（または病的な）木とは、各親ノードに関連付けられた子ノードが 1 つしかない木です。^[24]これは、木がリンク リストデータ構造のように動作することを意味します。この場合、バイナリ ツリーを使用する利点は大幅に減少します。これは、バイナリ ツリーが本質的にリンク リストであり、時間の計算量が O( n )（nはノードの数）であり、ノードごとに 2 つのポインタがあるため、リンク リストよりもデータ領域が大きいためです。一方、バランスの取れたバイナリ ツリーでのデータ検索の計算量は、通常、O(log ₂ n ) と予想されます。

• 完全二分木のノード数は、最小で で最大で（つまり、完全二分木のノード数）です。ここで は木の高さです。ルート ノードのみで構成される木の高さは 0 です。最小のノード数は、高さを追加するごとに 2 つの子ノードのみを追加することで得られます（ルート ノードを数える場合は 1）。最大ノード数は、各レベルのノードを完全に埋めることで得られます。つまり、完全木です。完全木の場合、ノード数は で、最後の等式は等比級数の和から得られます。${\displaystyle n}$${\displaystyle 2h+1}$${\displaystyle 2^{h+1}-1}$${\displaystyle h}$${\displaystyle 2h+1}$${\displaystyle 1+2+4+\ldots +2^{h}=2^{h+1}-1}$
• 完全な二分木の葉ノードの数は (ここで は木内のノードの数) です。これは(上記の性質を用いると)、葉の数が であるためです。これはまた を意味します。木の高さに関しては、です。${\displaystyle l}$${\displaystyle l=(n+1)/2}$${\displaystyle n}$${\displaystyle n={{2}^{h+1}}-1}$${\displaystyle 2^{h}}$${\displaystyle n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2}$${\displaystyle n=2l-1}$${\displaystyle h}$${\displaystyle l=(2^{h+1}-1+1)/2=2^{h}}$
• 葉ノードと次数 2 のノード (2 つの子ノードを持つ内部ノード) を持つ任意の空でない二分木について、です。 ^[25]証明は次のとおりです。完全二分木の場合、ノードの総数は(完全二分木は完全二分木です。) で、なので です。完全二分木から完全二分木を作成するには、2 つの兄弟ノードのペアを 1 つずつ削除します。これにより、「2 つの葉ノードが削除され」、「1 つの内部ノードが削除され」、「削除された内部ノードが葉ノードになる」ため、2 つの兄弟ノードを削除するごとに 1 つの葉ノードと 1 つの内部ノードが削除されます。結果として、完全二分木についても が成り立ちます。兄弟のない葉ノードを持つ二分木を作成するには、完全二分木から単一の葉ノードを削除し、「1 つの葉ノードが削除され」、「2 つの子を持つ 1 つの内部ノードが削除」されるため も成り立ちます。この関係は、空でないすべての二分木をカバーします。${\displaystyle l}$${\displaystyle i_{2}}$${\displaystyle l=i_{2}+1}$${\displaystyle n=2^{h+1}-1}$${\displaystyle l=2^{h}}$${\displaystyle i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1}$${\displaystyle l=i+1}$${\displaystyle l=i+1}$
• 与えられたノードで、ツリーがバランスのとれた完全なツリーまたは完全なツリーになる最小のツリーの高さは です。与えられた高さ で​​、ノードの数は、完全なツリーのノードの数として を超えることはできません。したがって です。${\displaystyle n}$${\displaystyle h_{min}=\log _{2}(n+1)-1}$${\displaystyle h}$${\displaystyle 2^{h+1}-1}$${\displaystyle n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1}$
• 葉のある二分木は、少なくとも高さ を持ちます。高さ が与えられた場合、その高さの葉の数は、完全な木の高さ の葉の数を超えることはできません。したがって です。${\displaystyle l}$${\displaystyle h_{m}=\log _{2}(l)}$${\displaystyle h}$${\displaystyle 2^{h}}$${\displaystyle l\leq 2^{h}\to h\geq \log _{2}(l)}$
• 空でない二分木では、がノードの総数で がエッジの総数である場合、 となります。これは、ルート ノードを除く各ノードに 1 つのエッジが必要であるため明らかです。${\displaystyle n}$${\displaystyle e}$${\displaystyle e=n-1}$
• n 個のノードの二分木におけるヌルリンク（つまり、ノードの存在しない子）の数は( n + 1) です。
• n個のノードを持つ完全二分木の内部ノードの数はです。${\displaystyle \lfloor n/2\rfloor }$

組合せ論では、与えられたサイズの完全な二分木の数を数える問題が考えられます。ここでは、木のノードに値は付いていません (これは、可能性のある木の数を、簡単に決定できる係数で乗算するだけです)。木は構造によってのみ区別されます。ただし、任意のノードの左の子と右の子は区別されます (これらが異なる木である場合、それらを入れ替えると、元の木とは異なる木が生成されます)。木のサイズは、内部ノード (子が 2 つあるノード) の数nとみなされます。その他のノードはリーフ ノードであり、n + 1個あります。サイズnのこのような二分木の数は、n個の二分演算子 (内部ノードを表す) で区切られた n + 1 個のシンボル (リーフを表す) の文字列を完全に括弧で囲む方法の数に等しく、これにより各演算子の引数部分式が決定されます。たとえば、n = 3の場合、 ⁠ ⁠のような文字列を括弧で囲む必要がありますが、これは 5 つの方法で可能です。 ${\displaystyle X*X*X*X}$

$${\displaystyle ((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).}$$

バイナリ ツリーへの対応は明らかである必要があり、冗長な括弧の追加 (すでに括弧で囲まれた式の周囲または完全な式の周囲) は許可されません (または少なくとも新しい可能性を生成するものとしてカウントされません)。

サイズ 0 の二分木 (単一の葉で構成) は 1 つだけ存在し、その他の二分木はいずれもその左と右の子のペアによって特徴付けられます。これらの子のサイズがそれぞれiとjの場合、完全な木のサイズはi + j + 1です。したがって、サイズnの二分木の数は、任意の正の整数nに対して、次のように再帰的に記述されます。したがって、はインデックスnのカタラン数です。 ${\displaystyle C_{n}}$${\displaystyle C_{0}=1}$${\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}$${\displaystyle C_{n}}$

上記の括弧で囲まれた文字列を、ダイク言語の長さ 2 nの単語の集合と混同しないでください。ダイク言語は、括弧のみで構成され、適切にバランスが取れています。このような文字列の数は、同じ再帰的記述を満たします (長さ 2 nの各ダイク単語は、最初の '(' と対応する ')' で囲まれたダイク部分単語と、その閉じ括弧の後に残るダイク部分単語によって決定され、その長さ 2 iと 2 j はi + j + 1 = n を満たします)。したがって、この数はカタロニア数でもあります。したがって、長さ 6 のダイク単語も 5 つあります。 ${\displaystyle C_{n}}$

()()()、()(())、(())()、(()())、((()))

これらの Dyck ワードは、同じようには二分木に対応しません。代わりに、これらは再帰的に定義された次の一対一の関係で関連付けられます。空の文字列に等しい Dyck ワードは、サイズ 0 で葉が 1 つだけの二分木に対応します。その他の Dyck ワードは ( )と記述できます。ここで、、はそれ自体 (空の場合もある) Dyck ワードであり、記述された 2 つの括弧は一致しています。次に、単語と をルートの左の子と右の子である二分木に対応させることで、一対一の関係が定義されます。 ${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle w_{1}}$${\displaystyle w_{2}}$

全単射対応は次のように定義することもできます。Dyck ワードをもう 1 組の括弧で囲むと、結果がLispリスト式 (空リスト () が唯一の出現アトム) として解釈されます。すると、その適切なリストのドット付きペア式は、対応するバイナリ ツリー (実際には適切なリストの内部表現) を記述する完全に括弧で囲まれた式 (記号として NIL、演算子として '.' を使用) になります。

バイナリ ツリーを記号と括弧の文字列として表現できるということは、バイナリ ツリーがシングルトン セット上の 自由マグマの要素を表現できることを意味します。

バイナリ ツリーは、プログラミング言語のプリミティブからいくつかの方法で構築できます。

レコードと参照を持つ言語では、バイナリ ツリーは通常、ツリー ノード構造によって構築されます。ツリー ノード構造には、データと、左の子と右の子への参照が含まれます。一意の親への参照が含まれる場合もあります。ノードの子が 2 つ未満の場合、子ポインタの一部が特別な null 値または特別なセンチネル ノードに設定されることがあります。

このバイナリツリーの保存方法では、ポインタが半分以上null（またはセンチネルを指す）になるため、かなりのメモリを無駄にします。より保守的な表現方法としては、スレッドバイナリツリーがあります。^[26]

MLのようなタグ付きユニオンを持つ言語では、ツリーノードは2種類のノードのタグ付きユニオンであることが多い。1つはデータ、左の子、右の子の3組であり、もう1つは「リーフ」ノードである。リーフノードにはデータは含まれず、ポインターを持つ言語のヌル値のように機能する。たとえば、OCaml（ML方言）の次のコード行は、各ノードに文字を格納するバイナリツリーを定義している。^[27]

型 chr_tree  = 空 |  char * chr_tree * chr_treeのノード      

二分木は、暗黙的なデータ構造として幅優先順序で配列に格納することもでき、木が完全な二分木である場合、この方法ではスペースが無駄になりません。このコンパクトな配置では、ノードがインデックスi を持つ場合、その子はインデックス(左の子の場合) と(右の子の場合) で見つかり、親 (存在する場合) はインデックス にあります(ルートのインデックスが 0 であると仮定)。代わりに、1 からインデックス付けされた配列では、実装は簡略化され、子はおよび、親はにあります。^[28]${\displaystyle 2i+1}$${\displaystyle 2i+2}$${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }$${\displaystyle 2i}$${\displaystyle 2i+1}$${\displaystyle \lfloor i/2\rfloor }$

この方法は、特に事前順序探索中に、よりコンパクトなストレージと参照の局所性が向上するという利点があります。バイナリヒープでよく使用されます。^[29]

簡潔なデータ構造とは、情報理論の下限によって確立された、可能な限り最小限のスペースを占める構造です。ノード上の異なる二分木の数は、番目のカタラン数です(同一の構造を持つ木を同一と見なすと仮定)。 が大きい場合、これは約 です。したがって、これをエンコードするには少なくとも約ビットが必要です。したがって、簡潔な二分木はビットを占めることになります。 ${\displaystyle n}$${\displaystyle \mathrm {C} _{n}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 4^{n}}$${\displaystyle \log _{2}4^{n}=2n}$${\displaystyle 2n+o(n)}$

この制限を満たす単純な表現の1つは、ツリーのノードを前順に訪問し、内部ノードの場合は「1」、リーフの場合は「0」を出力することです。^[30]ツリーにデータが含まれている場合は、それを前順に連続した配列に同時に格納するだけです。この関数はこれを実現します。

関数EncodeSuccinct(ノードn、ビット文字列構造、配列データ) {
     n = nilの場合 
        構造体に0を追加します。
    それ以外
        構造体に 1 を追加します。
        n.data をデータに追加します。
        EncodeSuccinct(n.left, 構造, データ);
        EncodeSuccinct(n.right、構造、データ);
}

文字列構造の最後にはビットのみがあり、これは(内部) ノードの数です。長さを保存する必要すらありません。情報が失われていないことを示すために、次のように出力を元のツリーに戻すことができます。 ${\displaystyle 2n+1}$${\displaystyle n}$

関数DecodeSuccinct(ビット文字列構造、配列データ) {構造
    の最初のビットを削除してb
    に格納し、b = 1の場合は
        新しいノードnを作成する
        データの最初の要素を削除し、n.dataに格納します。
        n.left = DecodeSuccinct(構造、データ)
        n.right = DecodeSuccinct(構造、データ)
        n
    を返すか、そうでない場合
        はn を返す
}

より洗練された簡潔な表現により、ツリーをコンパクトに保存できるだけでなく、簡潔な形式のままツリーに対して直接便利な操作を実行することもできます。

順序付きツリーと二分木の間には自然な一対一の対応関係があります。これにより、任意の順序付きツリーを二分木として一意に表現することができ、逆もまた同様です。

T を順序付きツリーのノードとし、Bを対応するバイナリ ツリーにおけるT のイメージとします。すると、 B の 左の子はT の最初の子を表し、B の右の子はT の次の兄弟を表します。

たとえば、左側の順序付きツリーと右側の二分木は次のように対応します。

図の二分木では、左の黒いエッジは最初の子を表し、右の青いエッジは次の兄弟を表します。

この表現は、左子右兄弟二分木と呼ばれます。

バイナリ ツリーに対して実行できる操作は多種多様です。ミューテーター操作もあれば、ツリーに関する有用な情報を返すだけの操作もあります。

ノードは、バイナリ ツリー内の他の 2 つのノードの間に挿入することも、リーフ ノードの後に​​追加することもできます。バイナリ ツリーでは、挿入されるノードは、誰の子になるかが指定されます。

リーフ ノード A の後に新しいノードを追加するには、A は新しいノードをその子ノードの 1 つとして割り当て、新しいノードはノード A をその親ノードとして割り当てます。

内部ノードへの挿入は、リーフ ノードへの挿入よりも少し複雑です。内部ノードがノード A で、ノード B が A の子であるとします (挿入が右の子を挿入するものである場合、B は A の右の子となり、左の子の挿入の場合も同様です)。A は子を新しいノードに割り当て、新しいノードは親を A に割り当てます。次に、新しいノードは子を B に割り当て、B は親を新しいノードとして割り当てます。

削除はツリーからノードを削除するプロセスです。バイナリツリー内の特定のノードのみが明確に削除できます。^[31]

削除するノードがノード A であるとします。A に子がない場合、削除は A の親の子をnullに設定することによって実行されます。A に子が 1 つある場合、A の子の親を A の親に設定し、A の親の子を A の子に設定します。

二分木では、2つの子を持つノードを明確に削除することはできません。^[31]ただし、特定の二分木（二分探索木を含む）では、ツリー構造を再配置することでこれらのノードを削除できます 。

事前順序、インオーダー、および事後順序のトラバーサルは、ルートの左側と右側のサブツリーの各ノードを再帰的に訪問することにより、ツリー内の各ノードを訪問します。以下は、上記のトラバーサルの簡単な説明です。

事前順序では、常に現在のノードにアクセスします。次に、現在のノードの左のサブツリーを再帰的にトラバースし、その後、現在のノードの右のサブツリーを再帰的にトラバースします。事前順序のトラバースは、親ノードが子ノードよりも先に処理されるため、トポロジ的にソートされたトラバースです。

in-order では、常に現在のノードの左のサブツリーを再帰的にトラバースします。次に、現在のノードにアクセスし、最後に、現在のノードの右のサブツリーを再帰的にトラバースします。

ポストオーダーでは、常に現在のノードの左サブツリーを再帰的にトラバースします。次に、現在のノードの右サブツリーを再帰的にトラバースしてから、現在のノードにアクセスします。ポストオーダートラバーサルは、バイナリ式ツリーのポストフィックス式を取得するのに役立ちます。^[32]

深さ優先順序では、常にルート ノードから可能な限り遠いノードを訪問しようとしますが、そのノードは既に訪問したノードの子でなければならないという注意点があります。グラフの深さ優先検索とは異なり、ツリーにはサイクルを含めることができないため、訪問したすべてのノードを記憶する必要はありません。事前順序は、この特別なケースです。詳細については、 深さ優先検索を参照してください。

深さ優先順序とは対照的に、幅優先順序では、ルートに最も近い、まだ訪問していないノードを常に訪問しようとします。詳細については、幅優先検索を参照してください。レベル順トラバーサルとも呼ばれます。

完全な二分木では、ノードの幅インデックス ( i − (2 ^d − 1)) をルートからのトラバーサル命令として使用できます。ビット d − 1 から始めて、左から右へビット単位で読み取ります。ここで、d はノードのルートからの距離 ( d = ⌊log 2 ( i +1)⌋) であり、問​​題のノードはルート自体ではありません ( d > 0)。幅インデックスがビットd − 1でマスクされ_ている場合、ビット値0と1はそれぞれ左または右に進むことを意味します。プロセスは、次のビットがなくなるまで右のビットを連続的にチェックすることによって続行されます。右端のビットは、目的のノードの親からノード自体への最終的なトラバーサルを示します。この方法で完全な二分木を反復処理することと、各ノードがその兄弟へのポインタを持つこととの間には、時間と空間のトレードオフがあります。

• ドナルド・クヌース著『コンピュータプログラミングの技法』第1巻、基礎アルゴリズム、第3版。Addison-Wesley、1997年。ISBN 0-201-89683-4。セクション2.3、特にサブセクション2.3.1～2.3.2（318～348ページ）。 

ウィキメディア・コモンズには、二分木に関連するメディアがあります。

• バイナリツリー 2020-09-23にアーカイブされたWayback Machineエントリ (FindStat データベース)
• 帰納法による二分木の証明
• 配列上のバランスのとれた二分探索木 ボトムアップの Ahnentafel リスト、または配列上のバランスのとれた二分探索木を作成する方法
• バイナリツリーとその実装、および実際のコード例
• ソースコード付きバイナリツリー JavaScript 実装