# 2015秋問３ 二分探索木の実装

class Node:
    def __init__(self, key):
        self.key = key      # ノードの値
        self.left = None    # 左の子への参照
        self.right = None   # 右の子への参照

# --- 探索：指定された値 k を持つノードを探す ---
def search(k, p):
    if p is None:           # 見つからなかった場合
        return None
    elif k == p.key:        # 値が一致（発見）
        return p
    elif k < p.key:         # 値が現在のノードより小さいなら左へ
        return search(k, p.left)
    else:                   # 値が現在のノードより大きいなら右へ
        return search(k, p.right)

# --- 追加：値 k を持つ新しいノードを適切な位置に挿入する ---
def addNode(k, p):
    if p is None:           # 空の位置に到達したら新しいノードを作成
        return Node(k)
    elif k != p.key:        # すでに同じ値がある場合は何もしない
        if k < p.key:       # 小さければ左に挿入
            p.left = addNode(k, p.left)
        else:               # 大きければ右に挿入
            p.right = addNode(k, p.right)
    return p

# --- 削除：値 k を持つノードを削除し、木を再構成する ---
def removeNode(k, p):
    if p is not None:
        if k < p.key:       # 削除対象が左にある場合
            p.left = removeNode(k, p.left)
        elif k > p.key:     # 削除対象が右にある場合
            p.right = removeNode(k, p.right)
        else:               # 削除対象のノード(p)を見つけた場合
            # ケース1 & 2: 子が1つ、または無い場合
            if p.left is None and p.right is None:
                p = None    # 葉ノードならそのまま削除
            elif p.left is None:
                p = p.right # 右の子を昇格させる
            elif p.right is None:
                p = p.left  # 左の子を昇格させる
            # ケース3: 子が2つある場合
            else:
                # 左部分木の中から最大値(extractMaxNode)を探して、現在の位置に置き換える
                p.left, r = extractMaxNode(p.left)
                r.left = p.left
                r.right = p.right
                p = r       # 最大値だったノードを現在の位置に据える
    return p

# --- 最大ノードの取り出し：指定されたノード以下の最大値を探して分離する ---
def extractMaxNode(p):
    if p.right is None:     # 右の子がいなければ、現在のノードが最大
        return p.left, p    # (自分の左の子, 自分自身) を返す
    else:
        # さらに右を探索しに行く
        p.right, r = extractMaxNode(p.right)
        return p, r

# --- 通りがかり順（中間順）巡回：昇順で値を表示する ---
def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)  # 左を先に処理
        print(node.key)               # 自分を表示
        inorder_traversal(node.right) # 右を後に処理

# --- メイン処理 ---
root = None
# データの挿入
for val in [5, 2, 7, 1, 8, 4, 3, 12]:
    root = addNode(val, root)

# ノードの削除（5:ルート, 7:子を持つノード）
root = removeNode(5, root)
root = removeNode(7, root)

# 結果の表示（二分探索木なので昇順に出力される）
inorder_traversal(root)