Pythonで二分木が赤黒木と同じように高さバランスされているかを判定する方法

問題の概要

赤黒木(Red-Black Tree)には「任意のノードにおける最大の高さは、最小の高さの2倍を超えない」という重要な性質があります。

この性質を一般の二分探索木に適用し、次の条件が成り立つかどうかを確認することを考えます。すべてのノードについて、そのノードから葉までの最長経路の長さが、最短経路上のノード数の2倍以下であること。

たとえば、次のような木が入力として与えられた場合、

この木はバランスが取れているため、出力は True になります。

解法のアプローチ

この問題は再帰的に解くことができます。手順は以下の通りです。

• 関数 solve() を定義します。引数は root(現在のノード)、max_height、min_height です。
• root が null の場合:
  • max_height := 0、min_height := 0 とする
  • True を返す
• left_max := 0、left_min := 0、right_max := 0、right_min := 0 で初期化します。
• solve(root.left, left_max, left_min) の結果が False の場合は False を返します。
• solve(root.right, right_max, right_min) の結果が False の場合も False を返します。
• max_height := 左右の最大値 + 1 を計算します。
• min_height := 左右の最小値 + 1 を計算します。
• max_height <= 2 * min_height が成り立てば True を返します。
• それ以外は False を返します。

メイン処理では、max_height と min_height を 0 で初期化し、solve(root, max_height, min_height) の結果を返します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

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

def solve(root, max_height, min_height):
    if (root == None):
        max_height = min_height = 0
        return True
    left_max = 0
    left_min = 0
    right_max, right_min = 0, 0
    if (solve(root.left, left_max, left_min) == False):
        return False
    if (solve(root.right, right_max, right_min) == False):
        return False
    max_height = max(left_max, right_max) + 1
    min_height = min(left_min, right_min) + 1
    if (max_height <= 2 * min_height):
        return True
    return False

def is_tree_balanced(root):
    max_height, min_height = 0, 0
    return solve(root, max_height, min_height)

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)
print(is_tree_balanced(root))

入力

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)

出力

True

まとめ

このアルゴリズムは、木を再帰的に走査しながら各部分木の最長・最短の高さを求め、「最長経路 ≤ 最短経路 × 2」という赤黒木の平衡条件を満たすかどうかを判定します。計算量は各ノードを一度ずつ訪問するため O(n) となり、効率的に木のバランス状態を確認できます。