# 2023a 二分探索木
class Node:
    """表1: 構造体 Node の定義"""
    def __init__(self, k):
        self.key = k
        self.left = None
        self.right = None

def height(t):
    """図7中で使われる関数 height: 木の高さを返す"""
    if t is None:
        return 0
    return 1 + max(height(t.left), height(t.right))

def rotateR(t):
    """図5: 右回転を行う関数"""
    a = t.left
    b = a.right
    a.right = t
    t.left = b
    return a

def rotateL(t):
    """図6: 左回転を行う関数"""
    a = t.right
    b = a.left
    a.left = t
    t.right = b
    return a

def balance(t):
    """図7: 関数 balance (平衡化処理)"""
    if t is None:
        return None

    # [ウ] 左の部分木が右より2高い場合
    h1 = height(t.left) - height(t.right)
    if h1 > 1:
        # [エ] 左の子の内部バランスを確認
        h2 = height(t.left.left) - height(t.left.right)
        if h2 < 0: # LR型: 先に左回転
            t.left = rotateL(t.left)
        t = rotateR(t)
    
    # [オ] 右の部分木が左より2高い場合
    elif h1 < -1:
        # [カ] 右の子の内部バランスを確認
        h3 = height(t.right.left) - height(t.right.right)
        if h3 > 0: # RL型: 先に右回転
            t.right = rotateR(t.right)
        t = rotateL(t)
        
    return t

def insertB(t, k):
    """図8: 平衡2分探索木への挿入関数"""
    if t is None:
        return Node(k)
    
    if k < t.key:
        t.left = insertB(t.left, k)
    elif k > t.key:
        t.right = insertB(t.right, k)
    
    # 挿入後に平衡化を行う
    return balance(t)

# --- 図1の木を再現 ---
# 根を6とし、3, 9, 1, 5 を挿入
r = None
for key in [6, 3, 9, 1, 5]:
    r = insertB(r, key)

print("--- 図1の状態 (初期状態) ---")
# 木の構造を簡易的に表示する関数
def print_tree(node, level=0, prefix="Root: "):
    if node:
        print("  " * level + prefix + str(node.key))
        if node.left or node.right:
            print_tree(node.left, level + 1, "L--- ")
            print_tree(node.right, level + 1, "R--- ")

print_tree(r)

# --- 設問2(2) の操作 ---
# insertB(insertB(r, 4), 8)
r = insertB(r, 4)
r = insertB(r, 8)

print("\n--- 操作後の木 (平衡化適用後) ---")
print_tree(r)