二分木の高さ — 木の深さの計算方法

二分木の高さの計算

二分木の高さは、ルートからリーフノードまでの最長パス上のエッジ数です。空の木の高さは 0、単一ノードの木の高さは 1（ノードを数える場合）または 0（エッジを数える場合）です。ここではノードを数えます。

再帰的な式

HEIGHT(node):
  if node is NULL: return 0
  left_height  = HEIGHT(node.left)
  right_height = HEIGHT(node.right)
  return 1 + max(left_height, right_height)

例

        4          高さ = 3
       / \
      2   6        左部分木の高さ = 2
     /             右部分木の高さ = 1
    1

HEIGHT(4) = 1 + max(HEIGHT(2), HEIGHT(6))
          = 1 + max(2, 1)
          = 3

高さ vs 深さ vs レベル

これらの用語はよく混同されます：

用語	定義
ノードの高さ	そのノードからリーフまでの最長パス
ノードの深さ	ルートからそのノードまでのパス長
レベル	深さ + 1（ルートはレベル 1）
木の高さ	ルートノードの高さ

BFS を使用した反復的アプローチ

レベル順走査を使用して反復的に高さを計算できます — レベル数が高さに等しい。

性能への影響

木の高さは BST 操作（探索、挿入、削除）の最悪ケースの時間計算量を直接決定します。バランスした木の高さは O(log n)、退化木の高さは O(n) です。これが自己平衡木（AVL、Red-Black）が重要な理由です。