7.1 二分木¶
二分木（binary tree）は、「祖先」と「子孫」の派生関係を表す非線形データ構造で、「一つを二つに分ける」という分割統治の論理を体現しています。連結リストと同様、基本単位はノードで、各ノードには値、左の子への参照、右の子への参照が含まれます。
/* 二分木のノードクラス */
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val; // ノードの値
this.left = left === undefined ? null : left; // 左の子への参照
this.right = right === undefined ? null : right; // 右の子への参照
}
}
use std::rc::Rc;
use std::cell::RefCell;
/* 二分木のノード構造体 */
struct TreeNode {
val: i32, // ノードの値
left: Option<Rc<RefCell<TreeNode>>>, // 左の子への参照
right: Option<Rc<RefCell<TreeNode>>>, // 右の子への参照
}
impl TreeNode {
/* コンストラクタ */
fn new(val: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self {
val,
left: None,
right: None
}))
}
}
/* 二分木のノード構造体 */
typedef struct TreeNode {
int val; // ノードの値
int height; // ノードの高さ
struct TreeNode *left; // 左の子へのポインタ
struct TreeNode *right; // 右の子へのポインタ
} TreeNode;
/* コンストラクタ */
TreeNode *newTreeNode(int val) {
TreeNode *node;
node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->height = 0;
node->left = NULL;
node->right = NULL;
return node;
}
各ノードは二つの参照（ポインタ）を持ち、それぞれ左の子ノード（left-child node）と右の子ノード（right-child node）を指します。そのノードは、二つの子の親ノード（parent node）と呼ばれます。あるノードの左の子とその下のノードが作る木を左部分木（left subtree）と呼び、同様に右部分木（right subtree）も定義できます。
二分木では、葉以外のすべてのノードが、子ノードと空でない部分木を持ちます。図 7-1 で「ノード 2」を親とすると、左右の子は「ノード 4」と「ノード 5」です。左部分木はノード 4 とその下のノードが作る木、右部分木はノード 5 とその下のノードが作る木です。
図 7-1 親ノード、子ノード、部分木
7.1.1 二分木の主な用語¶
主な用語を図 7-2 に示します。
- 根ノード（root node）：最上層にある、親を持たないノードです。
- 葉ノード（leaf node）：子を持たず、二つのポインタがどちらも
Noneを指すノードです。 - 辺（edge）：二つのノードを結ぶ線で、ノードの参照（ポインタ）です。
- ノードのレベル（level）：上から下へ増え、根のレベルは 1 です。
- ノードの次数（degree）：子ノードの数です。二分木では 0、1、2 のいずれかです。
- 二分木の高さ（height）：根から最も遠い葉までに通る辺の数です。
- ノードの深さ（depth）：根からそのノードまでに通る辺の数です。
- ノードの高さ（height）：そのノードから最も遠い葉と、そのノードとの間にある辺の数です。
図 7-2 二分木の主な用語
ヒント
通常、高さと深さは通る辺の数で定義しますが、問題や教科書によっては通るノードの数で定義する場合もあります。その場合は、高さと深さの両方に 1 を加えます。
7.1.2 二分木の基本操作¶
1. 二分木の初期化¶
連結リストと同じく、まずノードを初期化し、次に参照（ポインタ）をつなぎます。
// ノードを初期化
let n1 = TreeNode::new(1);
let n2 = TreeNode::new(2);
let n3 = TreeNode::new(3);
let n4 = TreeNode::new(4);
let n5 = TreeNode::new(5);
// ノード間の参照（ポインタ）をつなぐ
n1.borrow_mut().left = Some(n2.clone());
n1.borrow_mut().right = Some(n3);
n2.borrow_mut().left = Some(n4);
n2.borrow_mut().right = Some(n5);
実行の可視化
2. ノードの挿入と削除¶
連結リストと同様に、ポインタを変更してノードを挿入・削除できます。図 7-3 に例を示します。
図 7-3 二分木でのノードの挿入と削除
実行の可視化
ヒント
挿入は元の論理構造を変える可能性があり、削除は通常、そのノードとすべての部分木の削除を意味します。そのため、実際に意味のある操作を実現するには、複数の操作を組み合わせて挿入や削除を行うのが一般的です。
7.1.3 主な二分木の種類¶
1. パーフェクト二分木¶
図 7-4 のパーフェクト二分木（perfect binary tree）は、すべてのレベルが完全に埋まっています。葉の次数は \(0\)、ほかのすべてのノードの次数は \(2\) です。高さが \(h\) なら、総ノード数は \(2^{h+1} - 1\) という典型的な指数関係になり、自然界の細胞分裂に似た様子を示します。
ヒント
中国語圏では、パーフェクト二分木は「满二叉树」ともよく呼ばれます。
図 7-4 パーフェクト二分木
2. 完全二分木¶
図 7-5 の完全二分木（complete binary tree）では、最下層だけが完全に埋まっていなくてもよく、その層のノードは左から右へ連続して埋まっている必要があります。パーフェクト二分木も、完全二分木の一種です。
図 7-5 完全二分木
3. 全二分木¶
図 7-6 の全二分木（full binary tree）では、葉以外のすべてのノードが二つの子を持ちます。
図 7-6 全二分木
4. 平衡二分木¶
図 7-7 の平衡二分木（balanced binary tree）では、どのノードでも左右の部分木の高さの差の絶対値が 1 以下です。
図 7-7 平衡二分木
7.1.4 二分木の退化¶
図 7-8 は理想的な構造と退化した構造です。各層が埋まるとパーフェクト二分木になり、すべてのノードが一方に偏ると連結リストに退化します。
- パーフェクト二分木は理想的な場合で、分割統治の利点を十分に発揮できます。
- 連結リストはもう一方の極端な場合で、各操作が線形になり、時間計算量は \(O(n)\) に悪化します。
図 7-8 二分木の最良と最悪の構造
表 7-1 のように、最良と最悪の構造では、葉の数、総ノード数、高さなどが最大値または最小値になります。
表 7-1 二分木の最良と最悪の構造
| パーフェクト二分木 | 連結リスト | |
|---|---|---|
| 第 \(i\) レベルのノード数 | \(2^{i-1}\) | \(1\) |
| 高さ \(h\) の木の葉ノード数 | \(2^h\) | \(1\) |
| 高さ \(h\) の木の総ノード数 | \(2^{h+1} - 1\) | \(h + 1\) |
| 総ノード数 \(n\) の木の高さ | \(\log_2 (n+1) - 1\) | \(n - 1\) |