部分木（Subtree）は、グラフ理論とコンピュータサイエンスにおいて、木構造データの一部を構成する概念である。任意のノードを根とし、そのノードとすべての子孫ノード、およびそれらを結ぶエッジから成る部分グラフを指す。情報技術の分野では、二分木、B木、構文木などのデータ構造において、再帰的な操作（探索、挿入、削除）や部分問題の分解に広く利用される。部分木は、親木の構造特性（例：深さ、順序）を継承しつつ、独立した木としても機能する点が特徴である。
1 定義と基本概念
1.1 木構造における部分木の定義
木構造において、部分木とは、ある根ノードとそのすべての子孫ノード、およびそれらを結ぶ枝（エッジ）から構成される部分グラフである。形式的には、木 \( T = (V, E) \) に対して、ノード \( v \in V \) を根とする部分木 \( T_v \) は、\( v \) とそのすべての子孫からなる頂点集合 \( V' \subseteq V \) と、それらを結ぶ枝集合 \( E' \subseteq E \) で定義される。このとき、\( T_v \) はそれ自体が木構造をなす。
1.2 部分木とサブツリーの関係
「部分木」と「サブツリー」は同一概念を指す用語であり、いずれも木構造の一部を表す。英語の "subtree" に対する訳語として、日本語では「部分木」が一般に用いられるが、コンピュータサイエンスの文献では「サブツリー」も頻繁に使用される。両者は完全に同義であり、文脈に応じて使い分けられる。
1.3 根付き木における自然な部分木
根付き木（ルート付き木）では、任意のノードを根とすることで、一意に部分木が定まる。根ノードから始まる部分木は木全体と一致するが、葉ノードの部分木はノード単体となる。このように、木の再帰的構造に基づいて自然に抽出される部分木を「自然な部分木」と呼ぶことがある。自然な部分木は、親木の根からの距離（深さ）や子の順序を保持する。
2 部分木の種類
2.1 真部分木と空部分木
2.1.1 真部分木の条件
真部分木（proper subtree）とは、元の木全体とは異なる部分木である。任意のノード \( v \) を根とする部分木 \( T_v \) において、\( v \) が木全体の根でない場合、\( T_v \) は真部分木となる。真部分木は木全体から少なくとも一つのノードを除いたものであり、再帰的な分解の基礎となる。
2.1.2 空部分木の扱い
空部分木（empty subtree）は、ノードを含まない部分木を指す。特に二分木などでは、子を持たないノードの左部分木や右部分木を空部分木として明示的に扱う。空部分木はアルゴリズムの終了条件や基底ケースとして重要であり、ポインタや参照においては null や nil で表現される。
2.2 順序木における部分木
2.2.1 左部分木と右部分木
順序木、特に二分木では、各ノードが最大二つの子を持ち、左の子を根とする部分木を左部分木、右の子を根とする部分木を右部分木と呼ぶ。左部分木と右部分木の区別は、二分探索木や構文木において、要素の大小関係や演算子の優先順位を表現するために不可欠である。
2.2.2 多分木における子部分木
多分木（n分木）では、一つのノードが複数の子を持つ。各子を根とする部分木を「子部分木」と呼び、任意の子の数を \( k \) とした場合、\( k \) 個の子部分木が存在する。子部分木は順序を持つ場合と持たない場合があり、データ構造（例：B木）ではキー値によって子部分木が分割される。
3 部分木の操作と応用
3.1 再帰的アルゴリズムにおける部分木
3.1.1 深さ優先探索での部分木処理
深さ優先探索（DFS）では、木を再帰的に巡回する際に各部分木を独立した単位として扱う。DFS はルートから開始し、まず左部分木（または最初の子部分木）を完全に探索してから次の部分木へ移る。この過程で、部分木単位の訪問順序（先行順、中間順、後行順）が定義され、各種操作（値の集計、構造のコピーなど）に利用される。
3.1.2 動的計画法における部分問題分割
動的計画法（DP）では、木構造上の問題を部分木単位の部分問題に分割する。例えば、木の最大独立集合や木の直径を求める問題では、各部分木の解を再帰的に計算し、その結果を結合することで全体の解を得る。部分木の独立性が DP の適用を可能にする。
3.2 二分木における部分木
3.2.1 二分探索木の部分木操作
二分探索木では、部分木に対して探索、挿入、削除が再帰的に行われる。探索時には、キーとルートの比較に基づいて左または右の部分木に再帰する。挿入では、葉の位置に新しいノードを追加し、そのノードを根とする部分木を生成する。削除では、ノードの子の数に応じて部分木の再接続が必要となる。
3.2.2 平衡二分木（AVL木、赤黒木）での回転
AVL木や赤黒木などの平衡二分探索木では、部分木の高さのバランスを保つために「回転」操作が用いられる。回転は、あるノードを中心にその左右の部分木を再構成する操作であり、左回転と右回転がある。部分木の構造を変形させることで、木全体のバランスを維持する。
3.3 データベースとファイルシステムでの利用
3.3.1 B木における部分木分割
B木は多分木の一種であり、各ノードが複数のキーと子ポインタを持つ。B木の挿入操作では、ノードがオーバーフローした際に、ノードを二つの部分木に分割する。分割された部分木はそれぞれ独立したノードとして扱われ、親ノードに新しいキーが追加される。この部分木分割により、B木の高さバランスが保たれる。
3.3.2 ディレクトリ構造の部分木表現
ファイルシステムのディレクトリ構造は木として表現され、各サブディレクトリは部分木に対応する。パス指定は、ルートから目的のディレクトリまでの部分木の連続として解釈される。ディレクトリのコピーや移動は、部分木全体を対象とする操作として実装される。
4 部分木の数学的性質
4.1 部分木のサイズと高さ
部分木のサイズは、その部分木に含まれるノードの総数である。高さは、部分木の根から最も遠い葉までのエッジ数（またはノード数）で定義される。これらの量は、部分木の再帰的な性質から、親木のサイズや高さを計算する際の基本単位となる。例えば、木全体のサイズは、根の部分木のサイズに等しい。
4.2 同型な部分木とパターンマッチング
二つの部分木が同型（isomorphic）とは、その構造が同一であり、ノードの順序やラベルが一致する場合を指す。部分木の同型判定は、パターンマッチングや構文解析において重要であり、特に構文木では部分木の同型性を利用してコードの最適化や類似性の検出が行われる。
4.3 部分木の列挙と数え上げ問題
与えられた木に含まれるすべての部分木を列挙する問題は、組み合わせ論やアルゴリズムにおいて研究されている。特に二分木では、異なる部分木の総数はカタラン数に関連する。部分木の列挙は、木の構造解析や機械学習における特徴抽出の基礎となる。