1 木（ツリー）の基本
1.1 定義と直観
1.1.1 グラフとしての木
木は、計算機科学や離散数学で広く用いられる連結グラフの一種として捉えられる。直観的には「分岐していく道が、途中で合流して閉じた輪を作らない」構造である。形式的には、有限個の節をもち、辺によって節同士が結ばれているグラフのうち、閉路を含まず、全ての節が互いに到達可能であるものを木と呼ぶ。
この定義は、データ構造や探索アルゴリズムで扱う「階層の表現」と一致しやすい。情報は根から枝分かれしていき、どの節も（根を一意に定めれば）上流から一度だけ辿れるため、管理しやすい構造になる。
1.1.2 閉路がないことと経路の一意性
木の核心的な性質は、閉路を含まないことにある。閉路が存在しないため、任意の2節の間には、たどり方が過剰に競合せず、経路が一意に定まる。より具体的には、連結で閉路がないグラフでは、任意の節間の単純経路がちょうど1つ存在する。
この「経路の一意性」は、後の性質の同値条件の基盤になる。閉路が許される一般の連結グラフでは、2点間の行き方が複数になりうるため、探索や距離計算の見通しが変わる。
1.2 用語と表記
1.2.1 節（ノード）・辺（リンク）
木を構成する基本要素は節と辺である。節（ノード）は対象を表し、辺（リンク）は節同士のつながりを表す。木の文脈では、辺は一般に無向として扱われることが多いが、必要に応じて方向が与えられることもある。
記法としては、節集合をV、辺集合をEとし、グラフとして（V,E）の形で表すことが多い。実装では、各節が隣接する節の集合として表現されるため、隣接リストや隣接行列の形につながっていく。
1.2.2 根・親子関係・葉
根付き木では、特定の節を根として指定する。根を基準にすると、各節は根からの辿り方に沿って親子関係を持つ。ある節uから辺を通って到達できる節vのうち、根に近い側をuの「親」、vを「子」と呼ぶ。
子を持たない節は葉と呼ばれる。根付きの階層構造として解釈できる点が、木が探索や表現で便利になる理由の一つである。さらに、親子関係は経路の一意性に支えられるため、根を定めたときに関係はぶれない。
1.2.3 階層構造と深さ
根からの距離を段数として数える概念が深さである。根を深さ0とし、根からk本目の辺で到達できる節を深さkとする。深さは階層の「高さ」に対応し、木の形状や探索戦略の見積もりに関わる。
根から遠い節ほど深いという直観を保ちつつ、深さは深さ優先探索や動的計画法などの枠組みで中心的な指標になる。根付きでは節間の関係が階層化されるため、距離の意味が一層はっきりする。
1.3 性質の同値条件
1.3.1 連結で閉路がない
木の基本的な定義は「連結で閉路がない」である。ここから、閉路がないという制約が強力で、構造の自由度を大きく制限する。連結であるため孤立した部品は存在せず、閉路がないために回り道の選択肢も生まれない。
この条件は、同値な形に言い換えられることが多い。たとえば、連結性と閉路の不存在を別の統計量（節数と辺数）で捉えたり、到達可能性と分岐の規則性として表したりできる。以下では、その典型的な同値関係を整理する。
1.3.2 エッジ数と節数の関係
有限の木では、辺数mと節数nの間に明確な関係がある。具体的には、木は常にm = n − 1 を満たす。これは閉路がないことに由来する。閉路が存在すれば辺を増やしても新たな節に到達せずに回れるため、mがn−1を超える余地が生まれる。
逆に、連結でm = n − 1 が成立すれば閉路がないことが保証される。この「辺が1つ減るごとに、閉路が排除される」という感覚が、木を判定する手続きにもつながる。設計や検証の現場では、この関係が簡潔なチェックとして利用される。
2 木の代表的な種類
2.1 無根木と有根木
2.1.1 有根木の親子の定め方
無根木に対して根を選ぶことで、有根木が得られる。根の選択により親子関係は変化するが、元の無根構造は同一である。有根化の手続きは、根からの距離が小さい側を親とみなすことで一意に定まる。
実務上の選択としては、探索の出発点、階層モデルのトップ、データの基準点など、意味のある節を根に選ぶ。根を変更すると葉や深さの値は変わるが、経路の存在や分岐の有無といった骨格は保持される。
2.1.2 無根木での距離の考え方
無根木では方向づけがないため、深さのような概念は根を指定しない限り直接は定義できない。その代わり、距離は「2節間の辺数最小値」として扱う。木では経路が一意であるため、最小値という観点でも計算が単純になる。
距離は直径や中心など、形状の要約統計に発展しうる。例えば直径は最も距離が長い2点間の距離として定義される。こうした指標は、木の頑健性やネットワークの性能評価にも関係する。
2.2 二分木とその変種
2.2.1 完全二分木・完全（プロパー）二分木
二分木は各節が最大2つの子を持つ木である。完全二分木や完全（プロパー）二分木は、それぞれ形の条件で分類される。完全二分木は通常、最後の階層を除き全ての節が2つの子を持ち、最後の階層が左側から詰められているといった規則で特徴づけられる。
一方で「完全（プロパー）二分木」という語は文脈により微妙に定義が揺れることがあるが、一般には「葉以外の節がすべて2つの子を持ち」、かつ葉の出現が整った形になるような条件を指すことが多い。いずれの場合も、配列による表現と相性がよく、インデックスで親子関係を計算できる利点がある。
2.2.2 平衡二分木の考え方
平衡二分木は、探索時間を安定させるために形状の偏りを抑えようとする二分木の総称である。根から葉までの経路長が極端に伸びると、探索や挿入の効率が落ちるため、深さの差を制御する発想が導入される。
平衡の指標は実装方針に依存するが、例えば左右部分木の高さの差を制限する、または節の優先度に基づく回転操作を行って高さをならす、といった考え方がある。結果として、典型的な操作の計算量が対数オーダに保たれやすくなる。
2.3 多分木・根付き木
2.3.1 子の数と分岐数
多分木は各節が任意個数の子を持ちうる木である。分岐数は1つの節が持てる子の数、あるいは全体としての分岐の度合いを表す。二分木と比べて制約が緩いため、階層データの自然な写像先として選ばれやすい。
また、根付き木としての解釈では、各節の子集合が意味を持つ。たとえば文書の見出し構造、ファイルシステムのディレクトリ構造、計算式の部分式の構造などが、多分木の代表的な応用領域になる。
2.3.2 用途に応じた設計
木の設計は目的に応じて変わる。例えば探索を高速化したいなら、形状制御や追加情報（優先度、キー、集約値）を工夫する。更新が頻繁なら回転や再編のコストを抑える構成が求められる。
一方、データの表現が主目的の場合は、根付きで階層を明確にすることが重視される。さらに、サイズが大きい場合にはメモリ効率やキャッシュ局所性を意識した表現形式が選ばれる。木は「形」と「操作」の双方を設計対象にできる点が特徴である。
3 木の探索・走査
3.1 走査（トラバーサル）の基本
3.1.1 深さ優先探索（概念）
深さ優先探索は、根から出発し、できる限り先へ進んでから戻る方針の走査である。再帰呼び出しやスタックを使って実装されることが多い。根から辿る経路が長くなるため、深さが大きい木ではスタック消費が課題になりうる。
深さ優先は、部分構造を逐次処理するタスクに向く。たとえば、木を葉まで分解してから結果をまとめる動的計画法などで自然に利用できる。走査順は処理する節のタイミングによって複数の型に分かれる。
3.1.2 幅優先探索（概念）
幅優先探索は、根から距離（辺数）が等しい節を順番に処理する方針である。通常はキューを用い、最短距離が自然に反映される。無根木を有根化した状況で距離が明確になると、幅優先はレベルごとの集計に適する。
幅優先は、最短経路探索としても解釈される場合がある。木では経路が一意なので距離の意味が素直になり、探索の挙動が読みやすい。反面、同じ深さの節数が多い場合、保持する節が増えてメモリが膨らむことがある。
3.2 根付き木の順序付け
3.2.1 前順・中順・後順（概念整理）
根付き木で処理順を定める代表的な概念として、前順・中順・後順がある。厳密には二分木での呼び名として知られることが多いが、一般には「節を処理するタイミング」を軸に整理できる。前順は親を先に処理し、その後に部分木へ進む。中順は親と左右（または子の列）を交互に扱う型で、後順は親を最後に処理する。
この分類は、木の形状に従う再帰的定義を作る際に便利である。処理順が変わると得られる出力（例えば式の表現からの復元に関わる列）も変わるため、用途に応じて選択される。
3.2.2 レベル順の考え方
レベル順は幅優先に対応する概念で、根からの距離に基づき、同じ深さの節をまとめて処理する。根を含む最上位のレベルから順に下へ降りるため、階層の広がりを時系列に捉えやすい。
階層表示、レベルごとの集計、最初に到達する条件の判定などで使われる。特に出力が「層ごとの一覧」になる場合に直感的である。
3.3 計算量の見通し
3.3.1 節数と辺数による評価
木の探索・走査の計算量は、基本的に節数nと辺数mで評価できる。木ではm = n − 1 が成り立つため、走査ではしばしばO(n)での処理が見込まれる。各節を一度訪問し、各辺を定数回参照する設計にすると、全体の処理量が線形に収まる。
ただし実装上の詳細、例えば隣接リストで子の列をどのように保持しているか、あるいは探索中の判定にどれだけのコストがあるかで定数倍は変わる。計算量の見通しとしては「線形」だが、性能の実測では表現形式の影響が出やすい。
3.3.2 走査での注意点
走査では、再訪を避ける仕組みが必要になることがあるが、木は閉路を含まないため一般には単純化できる。根付きで親子関係が定められていれば、戻り先を親に限定でき、探索が迷いにくい。
それでも注意点は残る。例えば再帰実装は深い木でスタックオーバーフローの危険がある。幅優先はキューのサイズが最大でどれほどになるかを見積もる必要がある。さらに、走査順に依存して処理結果が変わるタスクでは順序選択が重要になる。
4 木の数え上げと応用
4.1 木の列挙問題（概要）
4.1.1 ラベル付きとラベルなし
木の列挙では、節に識別子（ラベル）を付けるかどうかが大きく結果を変える。ラベル付きでは、同型でもラベルの割り当てが異なれば別の対象として数えるため、数が増える。ラベルなしでは構造の形だけを区別し、同型とみなせるものは同一として扱う。
この差は、生成関数や数え上げ公式の作り方に反映される。ラベル付きでは対称性が弱く、局所的な構成を組み合わせる操作が扱いやすい。一方ラベルなしでは同型判定が絡み、理論的な取り扱いがより繊細になる。
4.1.2 構造の同型
構造の同型は、2つの木の間に節対応のずれがあっても、辺のつながり方が一致するなら同じとみなす考え方である。無根木では根なしの同型、根付き木では根を保存する同型が区別されることが多い。
同型の概念は数え上げの「同一視」に直結する。列挙の結果を解釈する際にも、ラベルの有無や根の固定条件を明確にしておく必要がある。
4.2 スパニングツリー
4.2.1 グラフから木を得る考え方
スパニングツリーは、ある連結グラフから節を全て含む木を取り出す考え方である。元のグラフに複数の経路がある場合、選ぶべき辺の集合をうまく絞ることで、閉路のない骨格を作れる。
この操作は「冗長性を落として重要な接続だけを残す」働きを持つ。ネットワーク設計では、全体をつなぎつつ回線数を抑える観点から意味がある。スパニングツリーはグラフの構造解析にも利用される。
4.2.2 最小全域木との関係（概観）
最小全域木は、辺に重みが与えられた連結グラフについて、スパニングツリーのうち重みの総和が最小のものを求める問題である。代表的な解法として、貪欲法を用いる手順や、辺の候補を段階的に絞る設計が知られている。
木の性質である閉路の排除は、最小化の手続きにも直結する。貪欲選択を行っても閉路が生じないよう管理することで、結果がスパニングツリーとして成立し、最終的に最小性が担保される。
4.3 組合せ論的な典型テーマ
4.3.1 カタラン数との関連（概念）
カタラン数は、多くの組合せ構造に現れる数列であり、二分木や整形式の親子関係などと結びつく。たとえば適切に条件をそろえた二分木の数え上げでは、カタラン数が現れることがある。
関連付けの背景には、構造の再帰的分解がある。ある節を基点にすると左右（または部分木）が独立に構成され、全体の数が「部分問題の組合せ」で表せるため、カタラン数の典型的な再帰式に近い形が得られることが多い。
4.3.2 木構造に基づく再帰の扱い
木は自然に再帰を誘発する。親を基準に部分木へ分解できるため、計算や数え上げが「下から上へ」組み立てられる。理論面では、再帰方程式や生成関数を用いて列挙を扱うことが多い。
実装面では、分岐ごとに同種の処理を適用し、結果を集約する枠組みが容易になる。動的計画法、木DP、あるいは式の評価などは、この再帰性を活用している。
4.4 データ構造としての木
4.4.1 優先度付き構造とのつながり
木は優先度と結びつくことで、効率よい操作が可能になることがある。典型例として、要素の大小関係や優先度に基づいて部分木の配置を制約することで、最小または最大の取り出しが速くなる構造がある。
こうした考え方では、木の形状と性質（順序関係）がセットで設計される。単なる階層表現ではなく、探索や取り出しの計算量を目的関数として扱うため、木は「データ配置のための器」として進化する。
4.4.2 検索・挿入・削除の基本的発想
木を使った基本操作は探索、挿入、削除である。検索は根から順に条件を満たす方向へ進み、該当節を見つける手続きとして定式化できる。挿入は空き位置に新しい葉を追加し、必要なら構造を整える。削除は節の取り除きに伴い、後続の整合性を保つために置換や再編を行う。
二分探索木や平衡木の発想では、これらの操作を対数時間程度に抑えることが目標になる。整列やインデックスの更新を繰り返す環境では、木が持つ階層と制約が性能の要となる。