Pythonで二分木が平衡（バランス）しているか判定する方法

平衡二分木（Height-Balanced Binary Tree）とは？

二分木では、各ノードは最大2つの子、すなわち「左の子」と「右の子」を持ちます。ある二分木が与えられたとき、その木が平衡（バランス）しているかどうかを判定することは、データ構造とアルゴリズムの学習における重要なテーマの一つです。

定義： すべてのノードについて、左部分木と右部分木の高さの差が「1」以下である場合、その二分木は平衡（height-balanced）であるとみなされます。

例1：平衡しているケース

入力：

        1
       / \
      2   3
         / \
        6   7

配列表現：[1, 2, 3, NULL, NULL, 6, 7]

出力：

True

説明： 左部分木（ノード2）の高さは1、右部分木（ノード3とその子6・7）の高さは2です。高さの差は「1」なので、この二分木は平衡しています。

例2：平衡していないケース

入力：

        1
       / \
      2   3
     /
    4
   /
  5

配列表現：[1, 2, 3, 4, NULL, NULL, NULL, 5]

出力：

False

説明： 左部分木の高さは3、右部分木の高さは1です。高さの差が「1」より大きいため、この二分木は平衡していません。

問題を解くアプローチ

最も直感的なのは再帰的なアプローチです。まず左部分木と右部分木それぞれの高さを求め、「height(左部分木) − height(右部分木) ≤ 1」が成り立つかどうかを確認します。条件を満たせば True を、満たさなければ False を返します。そして、このチェックを二分木のすべてのノードに対して再帰的に適用します。

• 二分木のノードを入力として受け取る。
• 木の高さを求める関数を定義する。
• 左部分木と右部分木の高さの差が「1」以下であれば True を返すブール関数を、再帰的に定義する。
• 結果を返す。

Pythonでの実装例

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 木の高さを求める関数
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

# 木が平衡しているかどうかを判定する関数
def isBalanced(root):
    if root is None:
        return True
    lh = height(root.left)   # 左部分木の高さ
    rh = height(root.right)  # 右部分木の高さ
    return (
        abs(lh - rh) <= 1
        and isBalanced(root.left)
        and isBalanced(root.right)
    )

# 動作確認用の二分木 [1, 2, 3, NULL, NULL, 6, 7]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

if isBalanced(root):
    print("Balanced")
else:
    print("Not Balanced")

上記のコードを実行すると、次の出力が得られます。

出力

Balanced

この二分木 [1, 2, 3, NULL, NULL, 6, 7] では、左部分木と右部分木の高さの差が「1」であるため、平衡二分木であると判定されました。

補足：計算量の改善

上記の実装では各ノードごとに高さを再計算するため、最悪の場合の時間計算量は O(n²) になります。高さの計算と平衡判定を同時に行うことで、O(n) まで効率化できます。

def checkBalance(root):
    # バランスが崩れている場合は -1 を返す
    if root is None:
        return 0
    lh = checkBalance(root.left)
    if lh == -1:
        return -1
    rh = checkBalance(root.right)
    if rh == -1:
        return -1
    if abs(lh - rh) > 1:
        return -1
    return max(lh, rh) + 1

def isBalancedFast(root):
    return checkBalance(root) != -1

この最適化版では、各ノードを一度だけ訪問すればよいため、大きな木でも高速に平衡判定を行えます。