DA:binarysearchtree

二分探索木

def insert(node, key):
    if node is None:
        return {"key": key, "left": None, "right": None}
    if key < node["key"]:
        node["left"] = insert(node["left"], key)
    elif key > node["key"]:
        node["right"] = insert(node["right"], key)
    return node

def search(node, key):
    if node is None:
        return False
    if key == node["key"]:
        return True
    elif key < node["key"]:
        return search(node["left"], key)
    else:
        return search(node["right"], key)

def delete(node, key):
    if node is None:
        return None
    if key < node["key"]:
        node["left"] = delete(node["left"], key)
    elif key > node["key"]:
        node["right"] = delete(node["right"], key)
    else:
        # 葉（子なし）の場合
        if node["left"] is None and node["right"] is None:
            return None
        # 子が一つの場合
        if node["left"] is None:
            return node["right"]
        if node["right"] is None:
            return node["left"]
        # 子が二つの場合
        successor = node["right"]
        while successor["left"]:
            successor = successor["left"]
        node["key"] = successor["key"]
        node["right"] = delete(node["right"], successor["key"])
    return node

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

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

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

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