二分木
サイズが 9、高さが 3 で、ルート ノードの値が 1 であるラベル付きバイナリ ツリー。上記のツリーはアンバランスであり、ソートされていません。
サイズが 9 (ツリー内のノードの数)、高さが 3 (最上位またはルート ノードから最も遠いリーフ ノードまでのエッジまたはリンクの数として定義されるツリーの高さ) で、ルート ノードの値が 1 であるラベル付きバイナリ ツリー。上記のツリーはアンバランスであり、ソートされていません。

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

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

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

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

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

定義

再帰定義

再帰的な完全木の定義

バイナリ ツリーを説明するシンプルで非公式なアプローチは次のようになります。

バイナリ ツリーにはルート ノードがあり、そのルート ノードには 0 個または 2 個の子ノードがあります (その子ノードにも 0 個または 2 個の子ノードがあります)。

より正式には：

この定義には2つの制限があります。完全な二分木には少なくとも1つのノードが含まれること、そしてどのノードも1つの子しか持つことができないことです。これは次の定義で解決されます。

再帰拡張ツリーの定義

拡張ツリーの定義は、ツリーが空になる可能性があるという仮定から始まります。

  • (基本ケース) 空のノード セットは拡張されたバイナリ ツリーです。
  • （再帰ステップ）T 1と T 2が拡張二分木であり、それらがどのノードも共有しておらず、rがそれらのいずれにも属さないノードである場合、順序付き3つ組（r、T 1、T 2）は拡張二分木である。[ 12 ] [ 11 ]

グラフの観点から完全であるためには、木の定義は両方とも、対応する枝集合の定義によって拡張される必要がある。非公式には、枝集合は、すべてのノードの順序付きペア(r, s)の集合として記述できる。ここで、rは定義に現れる任意の部分木のルートノードであり、sはその T 1および T 2部分木のいずれかのルートノードである（それぞれの部分木が空でない場合）。

この構成を想像する別の方法（および用語を理解する方法）は、空集合の代わりに異なるタイプのノード（たとえば、通常のノードが円である場合は正方形のノード）を考えることです。[ 13 ]

グラフ理論の概念の使用

二分木は根付き木であり、かつ順序付き木（平面木とも呼ばれる）でもあり、各ノードは最大2つの子を持つ。根付き木は自然にレベル（根からの距離）の概念を与える。したがって、各ノードに対して、1レベル下のノードとして子の概念を定義できる。これらの子を順序付け（例えば、平面上に描くなど）、左の子と右の子を区別することができる。[ 14 ]しかし、これでも左の子を持つが右の子を持たないノードと、右の子を持つが左の子を持たないノードを区別することはできない。

必要な区別は、まず辺を分割することによって行うことができる。つまり、二分木を三つ組 (V, E 1 , E 2 ) として定義する。ここで、 (V, E 1 ∪ E 2 ) は根付き木（樹状木と同等）であり、E 1 ∩ E 2は空であり、また、すべてのj ∈ { 1, 2 } に対して、すべてのノードは最大で 1 つの E j の子を持つ必要がある。[ 15 ]より非公式な方法で区別するには、数学百科事典を引用して、「すべてのノードは左の子、右の子、どちらも持たない、または両方を持つ」と述べ、これらが「すべて異なる」二分木であることを明記する。[ 7 ]

二分木の種類

ツリーの用語は十分に標準化されていないため、利用可能な文献の例によって異なる場合があります。

  • あ根付き二分木ルートノードがあり、各ノードには最大 2 つの子があります。
完全な二分木
完全な 4 レベルのバイナリ ツリーにマッピングできる家系図。
  • あ完全二分木（真、 [ 16 ]平面、または厳密二分木と呼ばれることもある） [ 17 ] [ 18 ]は、すべてのノードが0個または2個の子を持つ木である。完全二分木を定義する別の方法は再帰的定義。完全二分木は次のいずれかである。 [ 12 ]
    • 単一の頂点 (ルート ノードとしての単一のノード)。
    • ルート ノードに 2 つのサブツリーがあり、両方とも完全なバイナリ ツリーであるツリー。
  • あ完全二分木とは、全ての内部ノードが2つの子を持ち、全ての葉が同じ深さまたは同じレベル（ルートノードからノードまでのエッジまたはリンクの数として定義されるノードのレベル）を持つ二分木です。 [ 19 ]完全二分木は完全な二分木です。
  • あ完全二分木とは、最後のレベルを除くすべてのレベルが完全に埋められており、最後のレベルのすべてのノードが可能な限り左に配置されている最終レベルhには 1 ～ 2 個のhノードを持つことができます。 [ 20 ]そのため、完全木は常に完全ですが、完全木は常に完全であるとは限りません。一部の著者は、完全という用語を完全を指すために、その場合、このタイプの木（最終レベルが埋められていない可能性があります）をほぼ完全二分木またはほぼ完全二分木と呼びます。 [ 21 ] [ 22 ]完全二分木は、配列を使用して効率的に表すことができます。 [ 20 ]
完全な二分木（完全ではない）
  • 無限完全二分木は、各レベルdにおいて、レベル d に存在するノードの数が 2 dに等しいレベルを持つ木です。すべてのレベルの集合の基数は（可算無限）です。すべてのパス（いわゆる「葉」）の集合の基数は非可算であり、連続体の基数を持ちます。ℵ0{\displaystyle {\aleph_{0}}}ℵ0{\displaystyle {\aleph_{0}}}
  • バランスのとれた二分木とは、各ノードの左右のサブツリーの高さ（サブツリーの最上位ノードから最遠ノードまでの辺の数）の差が1以下（または偏りが1以下）である二分木構造である。[ 23 ]また、どの葉もルートから他の葉よりも極端に離れていない二分木も考えられる。（バランス調整スキームによって「極端に離れている」の定義は異なる。[ 24 ]）
  • 退化した（または病的な）木とは、各親ノードに関連付けられた子ノードが1つしかない木です。[ 25 ]これは、木がリンクリストデータ構造のように動作することを意味します。この場合、二分木を使用する利点は大幅に減少します。なぜなら、二分木は本質的にリンクリストであり、時間計算量はO( n )（nはノード数、'O()'はBig O記法）であり、ノードごとに2つのポインタがあるため、リンクリストよりもデータスペースが広くなるからです。一方、バランスの取れた二分木でのデータ検索の計算量は通常O(log2n ) と予想されます。

二分木の特性

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

組合せ論

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

（（X∗X）∗X）∗X、（X∗（X∗X））∗X、（X∗X）∗（X∗X）、X∗（（X∗X）∗X）、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のカタラン数です。 Cn{\displaystyle C_{n}}C0＝1{\displaystyle C_{0}=1}Cn＝∑私＝0n−1C私Cn−1−私{\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}Cn{\displaystyle C_{n}}

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

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

これらのダイク語は、二分木に同じようには対応しません。代わりに、それらは再帰的に定義された単射によって関連付けられます。空文字列に等しいダイク語は、葉が1つだけのサイズ0の二分木に対応します。その他のダイク語は ( )と表記できます。ここで、と はそれぞれ（空文字列も可）ダイク語であり、2つの括弧はそれぞれ対応しています。そして、単射は、と をルートの左右の子である二分木に対応させることによって定義されます。 わ1{\displaystyle w_{1}}わ2{\displaystyle w_{2}}わ1{\displaystyle w_{1}}わ2{\displaystyle w_{2}}わ1{\displaystyle w_{1}}わ2{\displaystyle w_{2}}

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

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

バイナリツリーの保存方法

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

ノードと参照

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

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

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

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

配列

二分木は、暗黙的なデータ構造として幅優先順序で配列に格納することもでき、木が完全二分木であれば、この方法では空間を無駄にしない。このコンパクトな配置では、ノードのインデックスがiの場合、その子ノードはインデックス（左の子ノードの場合）と（右の子ノードの場合）で見つかり、親ノード（存在する場合）はインデックス（ルートノードのインデックスが 0 であると仮定）で見つかる。あるいは、インデックスが 1 の配列の場合、実装は簡略化され、子ノードはと、親ノードは となる。[ 29 ]2私+1{\displaystyle 2i+1}2私+2{\displaystyle 2i+2}⌊私−12⌋{\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }2私{\displaystyle 2i}2私+1{\displaystyle 2i+1}⌊私/2⌋{\displaystyle \lfloor i/2\rfloor }

この手法は、特に事前順序探索において、よりコンパクトなストレージと優れた参照局所性という利点を持つ。バイナリヒープでよく用いられる。[ 30 ]

配列に格納された小さな完全な二分木
配列に格納された小さな完全な二分木

エンコーディング

簡潔なエンコーディング

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

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

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

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

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

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

順序木を​​二分木としてエンコードする

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

Tを順序木のノードとし、Bを対応する二分木におけるTの像とします。Bの左の子はTの最初の子を表し、Bの右の子はTの次の兄弟を表します。

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

n分木を二分木に変換する例
n分木を二分木に変換する例

図のバイナリ ツリーでは、左側の黒いエッジは最初の子を表し、右側の青いエッジは次の兄弟を表します。

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

一般的な操作

ツリーの回転は、自己バランス型バイナリツリーで非常に一般的な内部操作です。

二分木に対して実行できる操作には様々なものがあります。ミューテータ操作もあれば、単に木に関する有用な情報を返す操作もあります。

挿入

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

リーフノード

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

内部ノード

二分木にノードを挿入するプロセス

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

削除

削除とは、木からノードを取り除くプロセスです。二分木では、特定のノードだけが明確に取り除くことができます。[ 32 ]

0個または1個の子を持つノード

二分木の内部ノードを削除するプロセス

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

2つの子を持つノード

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

トラバーサル

事前順序、内順序、事後順序の探索は、ルートの左右のサブツリーの各ノードを再帰的に探索することで、ツリー内の各ノードを探索します。以下は、上記の探索の簡単な説明です。

予約注文

事前順序では、常に現在のノードにアクセスし、次に現在のノードの左サブツリーを再帰的に走査し、さらに現在のノードの右サブツリーを再帰的に走査します。事前順序走査は位相的にソートされた走査であり、親ノードは子ノードよりも先に処理されます。

順番に

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

後注文

後順では、常に現在のノードの左サブツリーを再帰的に走査し、次に現在のノードの右サブツリーを再帰的に走査し、最後に現在のノードを訪問します。後順走査は、二分式木の接尾辞式を取得するのに役立ちます。[ 33 ]

深さ優先順序

深さ優先探索では、ルートノードから可能な限り遠いノードを常に探索しようとしますが、そのノードは既に探索したノードの子ノードでなければならないという制約があります。グラフ上の深さ優先探索とは異なり、木構造には循環が含まれないため、探索したすべてのノードを記憶する必要はありません。事前順序探索は、この特殊なケースです。詳細については、 深さ優先探索を参照してください。

幅優先順序

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

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

参照

参考文献

引用

  1. ^ Rowan Garnier、John Taylor (2009). 『離散数学：証明、構造、応用、第3版』CRC Press. p. 620. ISBN 978-1-4398-1280-8。
  2. ^ Steven S Skiena (2009). 『アルゴリズム設計マニュアル』 Springer Science & Business Media. p. 77. ISBN 978-1-84800-070-4。
  3. ^ a b Knuth (1997). 『コンピュータプログラミングの芸術』第1巻、3/E . ピアソン・エデュケーション. p. 363. ISBN 0-201-89683-4。
  4. ^ Iván Flores (1971).コンピュータプログラミングシステム/360 . Prentice-Hall. p. 39.
  5. ^ケネス・ローゼン (2011). 『離散数学とその応用』第7版. マグロウヒル・サイエンス. p. 749. ISBN 978-0-07-338309-5。
  6. ^ David R. Mazur (2010).組合せ論：ガイドツアー. アメリカ数学会. p. 246. ISBN 978-0-88385-762-5。
  7. ^ a b「二分木」、数学百科事典、EMSプレス、2001 [1994]Michiel Hazewinkel (1997)としても出版されている。Encyclopaedia of Mathematics. Supplement I. Springer Science & Business Media. p. 124. ISBN 978-0-7923-4709-5。
  8. ^ LR Foulds (1992).グラフ理論応用. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3。
  9. ^ David Makinson (2009). Sets, Logic and Maths for Computing . Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6。
  10. ^ジョナサン・L・グロス (2007).コンピュータアプリケーションにおけるコンビナトリアルメソッド. CRC Press. p. 248. ISBN 978-1-58488-743-0。
  11. ^ a b Long, Chengjiang（2018年10月26日）、講義22：再帰的定義と構造的帰納法（PDF）
  12. ^ a bケネス・ローゼン (2011). 『離散数学とその応用 第7版』 マグロウヒル・サイエンス. pp.  352– 353. ISBN 978-0-07-338309-5。
  13. ^ Te Chiang Hu; Man-tak Shing (2002).組み合わせアルゴリズム. Courier Dover Publications. p. 162. ISBN 978-0-486-41962-6。
  14. ^ Lih-Hsing Hsu; Cheng-Kuan Lin (2008).グラフ理論と相互接続ネットワーク. CRC Press. p. 66. ISBN 978-1-4200-4482-9。
  15. ^ J. Flum; M. Grohe (2006).パラメータ化複雑性理論. Springer. p. 245. ISBN 978-3-540-29953-0。
  16. ^ Tamassia, Michael T. Goodrich, Roberto (2011).アルゴリズム設計：基礎、分析、そしてインターネットの事例（第2版）. ニューデリー: Wiley-India. p. 76. ISBN 978-81-265-0986-7。{{cite book}}: CS1 maint: multiple names: authors list (link)
  17. ^ 「完全二分木」。NIST 。
  18. ^リチャード・スタンレー『列挙的組合せ論』第2巻、36ページ
  19. ^「完全な二分木」。NIST 。
  20. ^ a b「完全二分木」。NIST。
  21. ^ 「ほぼ完全な二分木」 。 2016年3月4日時点のオリジナルよりアーカイブ。2015年12月11日閲覧。
  22. ^ 「ほぼ完全な二分木」（PDF）。2022年10月9日時点のオリジナルよりアーカイブ（PDF） 。
  23. ^ Aaron M. Tenenbaum他著『C言語によるデータ構造』Prentice Hall、1990年ISBN 0-13-199746-7
  24. ^ Paul E. Black (編)、「アルゴリズムとデータ構造辞書」のデータ構造の項目。米国国立標準技術研究所。2004年12月15日。オンライン版、 2010年12月19日アクセス。
  25. ^ Parmar, Anand K. (2020年1月22日). 「カラフルなイラスト付きでわかる様々な二分木の種類」 . Medium . 2020年1月24日閲覧。
  26. ^ Mehta, Dinesh; Sartaj Sahni (2004). 『データ構造とアプリケーションハンドブック』 . Chapman and Hall . ISBN 1-58488-435-5。
  27. ^ D. Samanta (2004).クラシックデータ構造. PHI Learning Pvt. Ltd. pp.  264– 265. ISBN 978-81-203-1874-8。
  28. ^ Michael L. Scott (2009).プログラミング言語語用論（第3版）. Morgan Kaufmann. p. 347. ISBN 978-0-08-092299-7。
  29. ^アルゴリズム入門. Cormen, Thomas H., Cormen, Thomas H. (第2版). Cambridge, Mass.: MIT Press. 2001. p. 128. ISBN 0-262-03293-7. OCLC  46792720 .{{cite book}}: CS1 maint: others (link)
  30. ^ラークソ、ミッコ。「プライオリティキューとバイナリヒープ」。アアルト大学。2023-10-11に取得。
  31. ^ Demaine, Erik. 「6.897: Advanced Data Structures Spring 2003 Lecture 12」(PDF) . MIT CSAIL. 2005年11月24日時点のオリジナル(PDF)からアーカイブ。 2022年4月14日閲覧。
  32. ^ a b Dung X. Nguyen (2003). 「二分木構造」 . rice.edu . 2010年12月28日閲覧。
  33. ^ Wittman, Todd (2015年2月13日). 「Lecture 18: Tree Traversals」(PDF) . 2015年2月13日時点のオリジナル(PDF)からアーカイブ。 2023年4月29日閲覧。

参考文献

ウィキメディア コモンズには、バイナリ ツリーに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Binary_tree&oldid=1332695704#perfect」から取得