二分木

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

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

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

コンピュータにおいて、二分木は大きく異なる2つの方法で使用できます。

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

樹木に関する用語は十分に標準化されていないため、既存の文献における例によって異なる場合がある。

• A根付き二分木は根ノードを持ち、各ノードは最大で2つの子ノードを持つ。

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

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

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

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

$${\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の二分木（単一の葉からなる）は一意に存在し、他の二分木は左右の子のペアによって特徴付けられます。これらの子のサイズがそれぞれiとjである場合、完全な木のサイズはi + j + 1になります。したがって、その数は${\displaystyle C_{n}}$サイズnの二分木は、以下の再帰的な記述を持つ。${\displaystyle C_{0}=1}$、 そして${\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}$任意の正の整数nに対して、次のことが成り立つ。${\displaystyle C_{n}}$は指数nのカタラン数である。^{[ 18 ]}

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

()()(), () (()), (())(), (()()), ((()))                

これらの Dyck 単語は、同じ方法では二分木に対応しません。代わりに、次の再帰的に定義された全単射によって関連付けられます。空文字列に等しい Dyck 単語は、葉が 1 つだけのサイズ 0 の二分木に対応します。他の Dyck 単語は次のように書くことができます (${\displaystyle w_{1}}$）${\displaystyle w_{2}}$、 どこ${\displaystyle w_{1}}$、${\displaystyle w_{2}}$はそれ自体が（おそらく空の）ディック語であり、2 つの書かれた括弧が一致する。その後、単語を${\displaystyle w_{1}}$そして${\displaystyle w_{2}}$ルートの左と右の子である二分木に対応する。

全単射対応は次のように定義することもできます。ディック語を括弧で囲み、結果をLispリスト式（空リスト()が唯一の出現アトム）として解釈できるようにします。すると、その適切なリストのドットペア式は、対応する二分木（実際には適切なリストの内部表現）を記述する、完全に括弧で囲まれた式（シンボルはNIL、演算子は'.'）になります。

二分木を記号と括弧の文字列として表現できるということは、二分木が単一要素集合上の自由マグマの要素を表現できることを意味する。

二分木は、プログラミング言語の基本要素を用いていくつかの方法で構築することができる。

type chr_tree = Empty | Node of char * chr_tree * chr_tree

配列

二分木は、幅優先順序で暗黙的なデータ構造として配列に格納することもできます。また、木が完全二分木の場合、この方法はスペースを無駄にしません。このコンパクトな配置では、ノードのインデックスがiの場合、その子はインデックス 1 で見つかります。${\displaystyle 2i+1}$（左の子供の場合）そして${\displaystyle 2i+2}$（右側の場合）一方、その親（存在する場合）はインデックスで見つかります${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }$（ルートのインデックスがゼロであると仮定します）。あるいは、1から始まるインデックスの配列では、子要素が次の位置にあるため、実装は簡略化されます。${\displaystyle 2i}$そして${\displaystyle 2i+1}$、親は以下で見つかりました${\displaystyle \lfloor i/2\rfloor }$[ ^{30 ]​}

この方法は、特に先行順走査の際に、よりコンパクトなストレージとより優れた参照の局所性という利点があります。バイナリヒープによく使用されます。^{[ 31 ]}

二分木に対しては、さまざまな操作を実行できます。中には変異操作もありますが、単に木に関する有用な情報を返すだけのものもあります。

挿入

ノードは、二分木内の他の2つのノードの間に挿入することも、葉ノードの後に​​追加することもできます。二分木では、挿入されるノードは、どのノードの子になるかが指定されます。

葉節

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

内部ノード

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

削除

削除とは、ノードをツリーから削除するプロセスです。二分木では、特定のノードのみを明確に削除できます。^{[ 33 ]}

子ノードが0個または1個しかないノード

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

2つの子ノードを持つノード

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

• バイナリツリーは、FindStatデータベースのWayback Machineエントリに2020年9月23日にアーカイブされました。
• 帰納法による二分木の証明（ 2019年4月7日にWayback Machineにアーカイブ済み）
• 配列上のバランスの取れた二分探索木 配列上にAhnentafelリストまたはバランスの取れた二分探索木をボトムアップで作成する方法
• 二分木とその実装例（動作コード例付き）
• 二分木とグラフの可視化ツール
• バイナリツリーのJavaScript実装（ソースコード付き）
• 二分木の上面図
• 二分木の底面図
• 二分木の左側面図