7.1 二分木¶
二分木は、祖先と子孫の間の階層関係を表現し、「二つに分割する」分割統治法の論理を体現する非線形データ構造です。連結リストと同様に、二分木の基本単位はノードであり、各ノードは値、左の子ノードへの参照、右の子ノードへの参照を含みます。
/* 二分木ノード */
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;
}
各ノードは2つの参照（ポインタ）を持ち、それぞれ左の子ノードと右の子ノードを指しています。このノードは、これら2つの子ノードの親ノードと呼ばれます。二分木のノードが与えられたとき、このノードの左の子とその下にあるすべてのノードで形成される木を、このノードの左部分木と呼びます。同様に、右部分木も定義できます。
二分木では、葉ノードを除いて、他のすべてのノードは子ノードと空でない部分木を含みます。 下図に示すように、「ノード2」を親ノードとして見ると、その左と右の子ノードはそれぞれ「ノード4」と「ノード5」です。左部分木は「ノード4」とその下にあるすべてのノードで形成され、右部分木は「ノード5」とその下にあるすべてのノードで形成されます。
図 7-1 親ノード、子ノード、部分木
7.1.1 二分木の一般的な用語¶
二分木でよく使用される用語を下図に示します。
- 根ノード：二分木の最上位レベルにあるノードで、親ノードを持ちません。
- 葉ノード：子ノードを持たないノードで、両方のポインタが
Noneを指しています。 - 辺：2つのノードを結ぶ線分で、ノード間の参照（ポインタ）を表現します。
- ノードのレベル：上から下に向かって増加し、根ノードがレベル1です。
- ノードの次数：ノードが持つ子ノードの数です。二分木では、次数は0、1、または2になります。
- 二分木の高さ：根ノードから最も遠い葉ノードまでの辺の数です。
- ノードの深さ：根ノードからそのノードまでの辺の数です。
- ノードの高さ：最も遠い葉ノードからそのノードまでの辺の数です。
図 7-2 二分木の一般的な用語
Tip
「高さ」と「深さ」は通常「通過する辺の数」として定義しますが、一部の問題や教科書では「通過するノードの数」として定義されることがあります。この場合、高さと深さの両方を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 二分木でのノードの挿入と削除
Tip
ノードの挿入は二分木の元の論理構造を変更する可能性があり、ノードの削除は通常そのノードとそのすべての部分木を削除することになることに注意してください。したがって、二分木では、挿入と削除は通常一連の操作を通じて実行され、意味のある結果を得ます。
7.1.3 二分木の一般的な種類¶
1. 完全二分木¶
下図に示すように、完全二分木では、すべてのレベルがノードで完全に埋められています。完全二分木では、葉ノードの次数は\(0\)で、他のすべてのノードの次数は\(2\)です。ノードの総数は\(2^{h+1} - 1\)として計算でき、ここで\(h\)は木の高さです。これは標準的な指数関係を示し、自然界の細胞分裂の一般的な現象を反映しています。
Tip
中国語圏では、完全二分木はしばしば満二分木と呼ばれることに注意してください。
図 7-4 完全二分木
2. 完備二分木¶
下図に示すように、完備二分木は、最下位レベルのみが完全に埋められていない可能性がある二分木で、最下位レベルのノードは左から右に連続して埋められる必要があります。完全二分木は完備二分木でもあることに注意してください。
図 7-5 完備二分木
3. 満二分木¶
下図に示すように、満二分木では、葉ノードを除いて、他のすべてのノードが2つの子ノードを持ちます。
図 7-6 満二分木
4. 平衡二分木¶
下図に示すように、平衡二分木では、任意のノードの左と右の部分木の高さの絶対差が1を超えません。
図 7-7 平衡二分木
7.1.4 二分木の退化¶
下図は、二分木の理想的な構造と退化した構造を示しています。二分木は、すべてのレベルが埋められているときに「完全二分木」になり、すべてのノードが一方に偏っているときに「連結リスト」に退化します。
- 完全二分木は、二分木の「分割統治法」の利点を十分に活用できる理想的なシナリオです。
- 一方、連結リストは別の極端を表し、すべての操作が線形になり、時間計算量が\(O(n)\)になります。
図 7-8 二分木の最良と最悪の構造
下表に示すように、最良と最悪の構造では、二分木は葉ノード数、総ノード数、高さの最大値または最小値を達成します。
表 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\) |