二分木の高さ
二分木の高さ
このレッスンで分かること
- 木の 高さ (height) は「根から葉までで一番長い経路に含まれるノード数」のことです
- 二分木の高さは、データ構造の 性能 に直結します
- 後のレッスンでやる「平衡判定」も、各ノードの左右の高さの差を見て判定します
二分木の高さ とは
二分木を配列表現で受け取り、根から葉までの最大のノード数 (高さ) を返す関数を実装する。本レッスンでは、二分木の高さ の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
木の 高さ (height) は「根から葉までで一番長い経路に含まれるノード数」のことです。例えば、ノード 1 つだけの木は高さ 1、空っぽの木は高さ 0、左右に 1 段子を持つ木は高さ 2 です。
高さは「最も深い葉までの段数」。ノード数で数える流儀 と 辺の数で数える流儀 があるが、本コースではノード数で統一する。
なぜ高さを計算したいのか
二分木の高さは、データ構造の 性能 に直結します。
- 高さ
hの二分探索木 (BST) では、検索・挿入の最悪計算量がO(h) - 平衡している木なら
h = O(log n)、退化しているとh = O(n) - ヒープや平衡木 (AVL, 赤黒木) は 高さを log n に保つ ことで性能を保証している
後のレッスンでやる「平衡判定」も、各ノードの左右の高さの差を見て判定します。つまり高さは 木のあらゆる解析の基礎 になる量です。
高さを
O(log n)に保つのが平衡木の使命。生 BST だと挿入順次第でO(n)まで悪化する。
例で確認する
[1, 2, 3, null, 4] の高さは？
- 葉
3までの経路 →1 → 3、ノード数2 - 葉
4までの経路 →1 → 2 → 4、ノード数3
最も長いのは 3。よって高さは 3 です。
他の例も見ておきましょう。
[1]→ 高さ1(ノード 1 つ)[](空) → 高さ0- 完全二分木
[1, 2, 3, 4, 5, 6, 7]→ 高さ3(log2(8) = 3)
Python での実装
再帰で書くのが定石です。post-order の典型例で、子の高さを取得してから親の高さを決めます。
Python
def height(tree):
def visit(i):
if i >= len(tree) or tree[i] is None:
return 0
left = visit(2 * i + 1)
right = visit(2 * i + 2)
return 1 + max(left, right)
return visit(0)ロジックは単純です。
- ノードが存在しない (
iが範囲外 orNone) → 高さ0 - それ以外 →
1 + max(左部分木の高さ, 右部分木の高さ)
+ 1 は 自分自身を 1 段としてカウント するためのものです。これを忘れると 辺の数 を返してしまいます。
JavaScript での実装
JavaScript
function height(tree) {
const visit = (i) => {
if (i >= tree.length || tree[i] === null) return 0;
const left = visit(2 * i + 1);
const right = visit(2 * i + 2);
return 1 + Math.max(left, right);
};
return visit(0);
}まったく同じ構造です。Math.max の引数は 2 つ で渡せば OK。Math.max(...arr) のように配列を展開する必要はありません。
反復で書く方法
反復で書くなら BFS を使い、レベルごとに進めた回数を数えます。
Python
from collections import deque
def height_iter(tree):
if not tree or tree[0] is None:
return 0
queue = deque([0])
h = 0
while queue:
h += 1
for _ in range(len(queue)):
i = queue.popleft()
for c in (2*i+1, 2*i+2):
if c < len(tree) and tree[c] is not None:
queue.append(c)
return hfor _ in range(len(queue)) のテクニックを覚えておくと、レベルごとの処理がきれいに書けます。BFS で「現在のレベルの全ノードを一度に処理」する常套句です。
よくある間違い
1 つ目は + 1 を忘れる。これだと辺の数になります (空木は -1 を返すことも)。2 つ目は 基底ケースを 1 にしてしまう。空ノードは 0、葉ノードが 1 です。3 つ目は max(left, right) を left + right にしてしまう。これは別の問題 (経路和) の話です。
やってみよう
- 高さ
nの 退化した木 (一直線) を作って計算してみる。[1, null, 2, null, null, null, 3, ...]のような形。 - 「木のサイズ (ノード数)」を計算する関数を書く。再帰の
1 + visit(left) + visit(right)で書ける。 - 「木の 直径 (任意の 2 つの葉間の最長経路)」を高さの計算と組み合わせて求めてみる。
O(n)で書けるはず。
高さの計算は post-order DP の最小単位。これを書けないとバランス判定も BST 検証も書けない。
よくある質問
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> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 二分木の平衡判定 で、各ノードの左右部分木の高さの差を調べて木がバランスしているかを判定する方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 木の高さ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 木の高さ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- ノードがない場合は高さ 0、ノード 1 つの場合は高さ 1 を返す
- 再帰または反復で実装すること
入出力例
test-cases.txt
height([1,2,3,null,4]) → 3
height([1]) → 1
height([1,2,3]) → 2
height([1,2,3,4,5,6,7]) → 3
height([1,null,2,null,null,null,3]) → 3
height([5,3,8,1,4,null,9]) → 3