2分木を理解する | ITQ Techpedia

1. 木構造について

　２分木（binary tree）について理解する前に、まずは木構造について確認していきます。

　木構造（Tree Structure）は、データ構造の一種であり、階層的な関係を表現するための非線形データ構造です。木構造は根（ルート）から始まり、枝（エッジ）によって複数の節（ノード）が接続され、最終的に葉（リーフ）と呼ばれる末端ノードに至ります。

　木構造はコンピュータサイエンスの基礎となる重要なデータ構造であり、ファイルシステム、データベースのインデックス、構文解析、検索アルゴリズムなど、多くの場面で応用されています。木構造を理解することは、効率的なアルゴリズムの設計や実装において不可欠です。

　木構造は以下の要素から構成されています。

図1: 木構造の基本用語

　ここまでの内容は、以下の「1.2.4. 木構造」でも解説しています。

　２分木（にぶんぎ）は、バイナリーツリー（binary tree）とも呼ばれます。
　各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造です。2分木はシンプルな構造ながら、多くの応用があります。

　今回の解説は、この２分木についてです。２分木には、主に次の３種類があります。

図２：完全２分木、満杯２分木、完璧２分木の比較図

　これだけだと、わかりにくいところもありますので例を示します。

　右のような完全２分木について、「１０」のノードを削除すると左のようになり、満杯２分木となります。葉の高さは揃っていませんが、子を持つノードはすべて０または２つのノードを持っています。（子が１のノードはありません）

図３：完全２分木から満杯２分木へ

　さらに「８」「９」を削除すると、完璧２分木となります。高さも揃って、完全に対象な形となり、完璧２分木です。

図４：完全２分木と完璧２分木

　さて、ここまでの説明だと「完璧２分木は、満杯２分木のサブセット？高さが揃えば、満杯２分木は完璧２分木？」と思えてしまいますが、そうではありません。以下にその例を示します。

図５：完璧２分木と満杯２分木と完全２分木

満杯二分木だが完全二分木ではない例：
- 各ノードは0個または2個の子を持つので満杯二分木
- しかし、左側（ノード2の下）に子がないのに右側（ノード3の下）に子がある
- これは「左から詰める」という完全二分木の条件に違反
完全二分木だが満杯二分木ではない例：
- 最後のレベル以外は完全に埋まっており、最後のレベルは左から詰められているので完全二分木
- しかし、ノード3が子を1つだけ（ノード6）持っている
- これは「0個または2個の子を持つ」という満杯二分木の条件に違反
両方の条件を満たす例：
- 完璧二分木は両方の条件を同時に満たしている

　満杯二分木が「各ノードが0個または2個の子を持つ」という条件に注目していることに対し、完全二分木は「最後のレベルを除くすべてのレベルが完全に埋まっている」かつ「最後のレベルは左から詰めて配置される」という、ノードの配置パターンに注目しています。

　今回の例で見たように、満杯二分木では「左から詰める」という制約がないため、左側に子がなくても右側に子を持つことができます。これが完全二分木の条件を満たさない理由となります。

　二分木の種類を理解する際には、これらの定義の微妙な違いを把握することが重要です。特にアルゴリズムやデータ構造を扱う際には、それぞれの特性を活かした実装が必要になることがあります。

　今回は、完全２分木、満杯２分木、完璧２分木についてみてきました。これらについて実務で深く突っ込むことはあまり多くないかと思いますが、このような違いのある間違えやすい用語があることから、齟齬が生じやすいところかと思います。

　迷ったときにはこの記事を思い出して再確認していただければ幸甚です。