DA:binarysearchtree

二分探索木

def insert(v, key):
    if v is None:
        return {"key": key, "left": None, "right": None}

    if key < v["key"]:
        v["left"] = insert(v["left"], key)

    elif key > v["key"]:
        v["right"] = insert(v["right"], key)

    return v

def search(v, key):
    if v is None:
        return False

    if key == v["key"]:
        return True

    elif key < v["key"]:
        return search(v["left"], key)

    else:
        return search(v["right"], key)

def delete(v, key):
    if v is None:
        return None

    if key < v["key"]:
        v["left"] = delete(v["left"], key)

    elif key > v["key"]:
        v["right"] = delete(v["right"], key)

    else:
        # 葉（子なし）の場合
        if v["left"] is None and v["right"] is None:
            return None

        # 子が一つの場合
        if ###ここを埋める###:
            return v["right"]
        if ###ここを埋める###:
            return v["left"]

        # 子が二つの場合
        tmp = ###ここを埋める###
        while ###ここを埋める###:
            tmp = ###ここを埋める###
        v["key"] = ###ここを埋める###
        v["right"] = ###ここを埋める###

    return v

def inorder(v):
    if v is None:
        return []
    return inorder(v["left"]) + [v["key"]] + inorder(v["right"])

# テストコード
tree = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree = insert(tree, value)

print("要素を整列して表示:", inorder(tree))
print("6を検索:", search(tree, 6))

tree = delete(tree, 10)
print("要素を整列して表示（10を削除後）:", inorder(tree))