二分木の平衡判定
二分木の平衡判定
このレッスンで分かること
- 二分探索木 (BST) の検索計算量は 木の高さに比例 します
- 二分木が 平衡 (balanced) であるとは、「すべてのノード で 左部分木の高さ と 右部分木の高さ の差が 1 以下」という状態を指します
- つまり同じ BST でも、平衡しているかどうかで 桁違いの性能差 が出ます
二分木の平衡判定 とは
二分木を配列表現で受け取り、すべてのノードで左右部分木の高さの差が 1 以下なら true を返す関数を実装する。
二分木が 平衡 (balanced) であるとは、「すべてのノード で 左部分木の高さ と 右部分木の高さ の差が 1 以下」という状態を指します。一部のノードだけ満たしていても、どこか 1 か所でも 差 >= 2 になっていれば平衡ではありません。
平衡判定は 全ノード で条件を満たすかをチェックする問題。1 か所でも崩れたら false。
なぜ平衡が重要か
二分探索木 (BST) の検索計算量は 木の高さに比例 します。
- 平衡な BST は
n個のノードに対し高さO(log n)→ 検索O(log n) - 退化した BST (一直線) は高さ
O(n)→ 検索O(n)
つまり同じ BST でも、平衡しているかどうかで 桁違いの性能差 が出ます。AVL 木や赤黒木、B-tree などの平衡木データ構造は、挿入のたびに自動で回転 して平衡を保つ仕掛けがあります。データベースのインデックスや std::map などの実装は基本的にこの系統です。
図のポイント (テキスト併記)
-
平衡木は 「最悪計算量を保証する」 ための CS 古典装置
平衡木は 「最悪計算量を保証する」 ための CS 古典装置。
std::map/ DB index の根っこにある。
例
[1, 2, 3, null, 4] の平衡判定をしてみます。
- 根
1左部分木 (2 → 4) の高さ2、右部分木 (3) の高さ1→ 差1、OK - ノード
2左nullの高さ0、右 (4) の高さ1→ 差1、OK - ノード
3、4葉なので OK
すべて条件を満たすので 平衡 (true)。
一方、[1, 2, null, 3] (root → left=2 → left=3 の一直線) は、根のところで左 2、右 0 → 差 2 で NG。
Python での実装 (O(n^2) 版)
まずは素直な実装から見てみます。
Python
def height(tree, i):
if i >= len(tree) or tree[i] is None:
return 0
return 1 + max(height(tree, 2*i+1), height(tree, 2*i+2))
def isBalanced(tree):
def check(i):
if i >= len(tree) or tree[i] is None:
return True
if abs(height(tree, 2*i+1) - height(tree, 2*i+2)) > 1:
return False
return check(2*i+1) and check(2*i+2)
return check(0)動きはしますが、各ノードで height を再計算 しているので計算量は O(n^2) です。
O(n) 版 (post-order トリック)
効率良くするには、再帰の戻り値に 「高さ」または「unbalanced のマーカー」 を載せます。
Python
def isBalanced(tree):
def visit(i):
if i >= len(tree) or tree[i] is None:
return 0
left = visit(2 * i + 1)
if left == -1:
return -1
right = visit(2 * i + 2)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return visit(0) != -1-1 を「unbalanced を表すセンチネル値」として使うアイデアです。一度どこかで unbalanced を見つけたら、それ以降は -1 を伝播させて全体を打ち切る ことができます。これで計算量は O(n) に落ちます。
「異常を表すセンチネル」を再帰の戻り値に混ぜるテクは、tree DP / graph DP で頻出。
JavaScript での実装
JavaScript
function isBalanced(tree) {
const visit = (i) => {
if (i >= tree.length || tree[i] === null) return 0;
const left = visit(2 * i + 1);
if (left === -1) return -1;
const right = visit(2 * i + 2);
if (right === -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
};
return visit(0) !== -1;
}戻り値の流儀は同じです。-1 を見たら即座に親へ伝播させて、それ以上の計算を省略しています。
よくある間違い
1 つ目は 「根だけチェックする」。平衡は 全ノード の条件です。根の左右が差 1 以下でも、深いところで崩れていれば false。2 つ目は abs を忘れる。差は絶対値で見ます。3 つ目は O(n^2) 解を提出して timeout する。木が大きいとノード数の 2 乗に比例して遅くなるので、post-order でセンチネル -1 を使う形を覚えておきましょう。
やってみよう
[1, 2, 3, 4, 5, 6, 7](完全二分木) の平衡判定をする →true。[1, 2, null, 3, null, null, null, 4]のような左に偏った木 →false。- AVL 木のコードを読んでみる。挿入時に 回転 で平衡を保つ仕掛けが見える。
「全ノードで局所条件を満たすか」を post-order で
O(n)で判定する、はこのレッスンで習得したい必勝パターン。
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 第2章まとめクイズ — 二分木 で、二分木を配列表現で受け取り、すべてのノードで左右部分木の高さの差が 1 以下なら true を返す関数を実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 平衡判定 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 平衡判定 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 全ノードで左右部分木の高さの差が 1 以下なら true を返す
- 空の木 ([]) や [null] は true として扱う
入出力例
test-cases.txt
isBalanced([1,2,3,null,4]) → true
isBalanced([1]) → true
isBalanced([1,2,3,4,5,6,7]) → true
isBalanced([1,2,null,3]) → false
isBalanced([1,null,2,null,null,null,3]) → false
isBalanced([1,2,3,4,null,null,null,5]) → false