Problem:

Binary Search Tree III

Write a program which performs the following operations to a binary search tree $T$ by adding delete operation to B: Binary Search Tree II.

  
insert  $k$: Insert a node containing $k$ as key into $T$.

  
find $k$: Report whether $T$ has a node containing $k$. 

  
delete $k$: Delete a node containing $k$.

  
print: Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.

The operation delete $k$ for deleting a given node $z$ containing key $k$ from $T$ can be implemented by an algorithm which considers the following cases:

 If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).

 If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.

 If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.

Input

   In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$, delete $k$ or print are given.

Output

For each find $k$ operation, print "yes" if $T$ has a node containing $k$, "no" if not.

  In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key

Constraints

   
The number of operations $\leq 500,000$

The number of print operations $\leq 10$.

  
$-2,000,000,000 \leq key \leq 2,000,000,000$

  
The height of the binary tree does not exceed 100 if you employ the above pseudo code.

The keys in the binary search tree are all different.

Sample Input 1

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

Sample Output 1

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print


Sample output:
yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
print = sys.stdout.write

class Node:
    __slots__ = ["data", "left", "right"]
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        parent = self.root
        if parent is None:
            self.root = Node(data)
            return
        while parent:
            parent_old = parent
            parent = parent.left if data < parent.data else parent.right
        if data < parent_old.data:
            parent_old.left = Node(data)
        else:
            parent_old.right = Node(data)
        
    def find(self, data):
        parent = self.root
        if parent is None:
            print("no\n")
            return
        while parent:
            if parent.data == data:
                print("yes\n")
                return
            parent = parent.left if data < parent.data else parent.right
        print("no\n")
        return
    
    def delete(self, data):
        target = self.root
        if target is None:
            return
        while target:
            if target.data == data:
                if target.right and target.left:
                    next_target = target.right
                    if next_target.left is None:
                        if target == self.root:
                            self.root = next_target
                        target.data = next_target.data
                        target.right = next_target.right
                        return
                    while next_target.left:
                        parent = next_target
                        next_target = next_target.left
                    if target == self.root:
                        self.root = next_target
                    target.data = next_target.data
                    parent.left = next_target.right
                    return
                else:
                    child = target.right or target.left
                    if target == self.root:
                        self.root = child
                        if child is None:
                            return
                    if child:
                        target.data, target.left, target.right = child.data, child.left, child.right
                    else:
                        if data < parent.data:
                            parent.left = None
                        else:
                            parent.right = None
                    return
            parent = target
            target = target.left  if data < target.data else target.right


def print_preorder(node):
    print(" {}".format(node.data))
    if node.left:
        print_preorder(node.left)
    if node.right:
        print_preorder(node.right)

def print_inorder(node):
    if node.left:
        print_inorder(node.left)
    print(" {}".format(node.data))
    if node.right:
        print_inorder(node.right)

if __name__ == "__main__":
    n = int(input())
    binary_search_tree = BinarySearchTree()
    for _ in range(n):
        operation, *num = input().split()
        if operation[0] == "i":
            binary_search_tree.insert(int(num[0]))
        elif operation[0] == "f":
            binary_search_tree.find(int(num[0]))
        elif operation[0] == "d":
            binary_search_tree.delete(int(num[0]))
        elif binary_search_tree.root is not None:
            print_inorder(binary_search_tree.root)
            print("\n")
            print_preorder(binary_search_tree.root)
            print("\n")

Submission status: Accepted

Solution code:
def preParse(u):
    if u == None:
        return
    print(' {}'.format(u), end='')
    preParse(nodes[u][1])
    preParse(nodes[u][2])

def inParse(u):
    if u == None:
        return
    inParse(nodes[u][1])
    print(' {}'.format(u), end='')
    inParse(nodes[u][2])

def printTree(root):
    inParse(root)
    print()
    preParse(root)
    print()

def insert(nodes,z,root):
    x = root
    y = None
    while x != None:
        y = x
        if z < x:
            x = nodes[x][1]
        else:
            x = nodes[x][2]
    nodes[z][0] = y

    if y == None:
        root = z
    elif z < y:
        nodes[y][1] = z
    else:
        nodes[y][2] = z
    return root

def find(nodes,z,root):
    x = root
    while x != None and z != x:
        if z < x:
            x = nodes[x][1]
        else:
            x = nodes[x][2]
    return x

def getMinimum(nodes,x):
    while nodes[x][1] != None:
        x = nodes[x][1]
    return x

def getSuccessor(nodes,x):
    if nodes[x][2] != None:
        return getMinimum(nodes,nodes[x][2])
    
    y = nodes[x][0]
    while y != None and z == nodes[y][2]:
        x = y
        y = nodes[y][0]
    return y

def deleteNode(nodes,z,root):
    # 削除する対象をyとする
    if nodes[z][1] == None or nodes[z][2] == None:
        y = z
    else:
        y = getSuccessor(nodes,z)

    # yの子xを決める
    if nodes[y][1] != None:
        x = nodes[y][1]
    else:
        x = nodes[y][2]

    # xの親を設定する
    if x != None:
        nodes[x][0] = nodes[y][0]

    # yが根の時、xを木の根とする
    if nodes[y][0] == None:
        root = x
    # yがその親pの左の子なら、pの左の子をxとする
    elif y == nodes[nodes[y][0]][1]:
        nodes[nodes[y][0]][1] = x
    # yがその親pの右の子なら、pの右の子をxとする
    else:
        nodes[nodes[y][0]][2] = x
    
    # zの次節点の連結が解除された場合、yにzのデータをコピーし、
    # zに親子がいた場合はその親子に対してzの部分をyで置き換える
    # これによって、zの部分がまるでyに置き換わったように扱え、zが削除されたことになる
    if y != z:
        nodes[y] = nodes[z]
        if nodes[y][0] != None:
            if nodes[nodes[y][0]][1] == z:
                nodes[nodes[y][0]][1] = y
            else:
                nodes[nodes[y][0]][2] = y
        if nodes[y][1] != None:
            nodes[nodes[y][1]][0] = y
        if nodes[y][2] != None:
            nodes[nodes[y][2]][0] = y

    return root


nodes = {}

# {key:[parent,left,right]}

N = int(input())

root = None

for i in range(N):
    order = input().split()
    if order[0] == 'print':
        printTree(root)
        continue

    z = int(order[1])
    if order[0] == 'insert':
        nodes[z] = [None,None,None]
        root = insert(nodes,z,root)
        continue

    if order[0] == 'find':
        k = find(nodes,z,root)
        if k == z:
            print('yes')
        else:
            print('no')
        continue

    if order[0] == 'delete':
        root = deleteNode(nodes,z,root)
        continue

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.order_list = []
    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def find(self, key):
        x = self.root
        while x != None:
            if key == x.key:
                return x
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return None
    def delete(self, z):
        if z.left == None and z.right == None:
            if z.key < z.parent.key:
                z.parent.left = None
            else:
                z.parent.right = None
        elif z.left != None and z.right == None:
            z.left.parent = z.parent
            if z.key < z.parent.key:
                z.parent.left = z.left
            else:
                z.parent.right = z.left
        elif z.left == None and z.right != None:
            z.right.parent = z.parent
            if z.key < z.parent.key:
                z.parent.left = z.right
            else:
                z.parent.right = z.right
        else:
            next_node = z.right
            while next_node.left:
                next_node = next_node.left
            z.key = next_node.key
            self.delete(next_node)
            
    def walk_preorder(self, node):
        if node == None:
            return None
        self.order_list.append(node.key)
        self.walk_preorder(node.left)
        self.walk_preorder(node.right)
    def walk_inorder(self, node):
        if node == None:
            return None
        self.walk_inorder(node.left)
        self.order_list.append(node.key)
        self.walk_inorder(node.right)
    def print_nodes(self):
        self.order_list = []
        self.walk_inorder(self.root)
        inorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(inorder_str))
        self.order_list = []
        self.walk_preorder(self.root)
        preorder_str = ' '.join(map(str, self.order_list))
        print(' {}'.format(preorder_str))
        
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

n = int(input())
tree = BinarySearchTree()
for _ in range(n):
    command = input().split(' ')
    if len(command) == 1:
        tree.print_nodes()
    else:
        opecode, operand = command[0], int(command[1])
        if opecode == 'insert':
            node = Node(operand)
            tree.insert(node)
        elif opecode == 'find':
            node = tree.find(operand)
            if node != None:
                print('yes')
            else:
                print('no')
        elif opecode == 'delete':
            node = tree.find(operand)
            if node != None:
                tree.delete(node)

Submission status: Accepted

Solution code:
"""
ALDS1_8_C
螺旋本を参考にしています
"""
import copy

class Node:
    def __init__(self, node_id, parent=None, left=None, right=None):
        self.node_id = node_id
        self.parent = parent
        self.left = left
        self.right = right

class Tree:
    def insert_root_node(self, new_id):
        global root_node 
        root_node = Node(new_id)

    def insert_node(self, new_id): 
        compare_node = root_node 
        new_node = Node(new_id)
        while compare_node is not None: 
            new_node.parent = compare_node 
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        if new_node.parent.node_id < new_id:
            new_node.parent.right = new_node
        else:
            new_node.parent.left = new_node


    def find(self, search_id):
        tmp_node = root_node
        while tmp_node:
            if tmp_node.node_id == search_id:
                print('yes')
                return
            elif tmp_node.node_id < search_id:
                tmp_node = tmp_node.right
            else:
                tmp_node = tmp_node.left
        print('no')

    #search_nodeを根とする右部分技の最も小さいノードを取得する
    def getTheLeft(self, search_node): 
        while search_node.left:
            search_node = search_node.left
        return search_node

    def delete(self, search_id):
        tmp_node = root_node
        while tmp_node:
            if tmp_node.node_id == search_id:
                if tmp_node.left is None and tmp_node.right is None:
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = None
                    else:
                        tmp_node.parent.left = None
                    return
                elif tmp_node.left is None and tmp_node.right is not None:
                    tmp_node.right.parent = tmp_node.parent
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = tmp_node.right
                    else:
                        tmp_node.parent.left = tmp_node.right
                    return
                elif tmp_node.left is not None and tmp_node.right is None:
                    tmp_node.left.parent = tmp_node.parent
                    if tmp_node.parent.node_id < search_id:
                        tmp_node.parent.right = tmp_node.left
                    else:
                        tmp_node.parent.left = tmp_node.left
                    return
                else:
                    left_node = tmp_node.right
                    left_node = self.getTheLeft(left_node) 
                    if left_node.parent.node_id < left_node.node_id: 
                        left_node.parent.right = None
                        left_node.parent = None
                    else:
                        left_node.parent.left = None
                        left_node.parent = None
                    tmp_node.node_id = left_node.node_id
                    return

            elif tmp_node.node_id < search_id:
                tmp_node = tmp_node.right
            else:
                tmp_node = tmp_node.left
#------------------------------------------------

def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)

#------------------------------------------------


tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if not root_node: #何も入ってない時
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()
    elif order[0][0] == 'f':
        tree.find(int(order[1]))
    elif order[0][0] == 'd':
        tree.delete(int(order[1]))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None

    def _get_most_left_node(self):
        x = self
        while x.left is not None:
            x = x.left
        return x
    
class Tree():
    def __init__(self, root=None):
        self.root = root
    
    def insert(self, node):
        y = None
        x = self.root
        while x is not None:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
        
        node.parent = y
        if y is None:   # Tree が空だった場合
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node
    
    def print_inorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            work(node.left)
            print('', node.key, end='')
            work(node.right)

        work(self.root)
        print()
    
    def print_preorder_tree_walk(self):
        def work(node):
            if node is None:
                return
            print('', node.key, end='')
            work(node.left)
            work(node.right)

        work(self.root)
        print()

    def find(self, key):
        """Tree 中に key をもつノードがあればそのノードを返す。なければ None を返す。"""
        x = self.root
        while x is not None:
            if key == x.key:
                return x
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return None

    def delete(self, key):
        """削除できたら True、存在せず削除できない場合は False を返す。"""
        x = self.find(key)
        if not x:
            return False
        y = x if x.left is None or x.right is None else x.right._get_most_left_node()
        z = y.left if y.left is not None else y.right
        if z is not None: z.parent = y.parent
        if y.parent is None:
            self.root = z
        elif y is y.parent.left:
            y.parent.left = z
        else:
            y.parent.right = z
        
        if x is not y:
            x.key = y.key
        
        return True

if __name__ == '__main__':
    import sys

    n = int(input())
    T = Tree()
    for _ in range(n):
        command, *args = sys.stdin.readline().split()
        if command[0] == 'i':   # insert key
            T.insert(Node(int(args[0])))
        elif command[0] == 'f': # find key
            if T.find(int(args[0])):
                print('yes')
            else:
                print('no')
        elif command[0] == 'd': # delete key
            T.delete(int(args[0]))
        else:   # print
            T.print_inorder_tree_walk()
            T.print_preorder_tree_walk()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right

    def is_root(self):
        return self.parent is None

    def num_children(self):
        count = 0
        if self.left is not None:
            count += 1
        if self.right is not None:
            count += 1
        return count

    def has_left(self):
        return self.left is not None

    def has_right(self):
        return self.right is not None

    def has_parent(self):
        return self.parent is not None

    def __key(self, obj):
        if isinstance(obj, int):
            return obj
        if isinstance(obj, Node):
            return obj.key

class Tree():
    def __init__(self, num_list=[]):
        self.root = None
        for num in num_list:
            self.insert(num)

    def is_empty(self):
        return self.root is None

    def insert(self, key):
        parent = None
        target = self.root
        while target is not None:
            parent = target
            if key < target.key:
                target = target.left
            else:
                target = target.right
        node = Node(key, parent)
        if node.is_root():
            self.root = node
        elif node.key < parent.key:
            parent.left = node
        else:
            parent.right = node

    def find(self, key):
        if self.is_empty():
            return None
        else:
            node = self.root
            while node is not None:
                if key == node.key:
                    return node
                elif key < node.key:
                    node = node.left
                else:
                    node = node.right
            return node

    def __preorder(self, node):
        if node is None:
            return []
        return [node.key] + self.__preorder(node.left) + self.__preorder(node.right)

    def __inorder(self, node):
        if node is None:
            return []
        return self.__inorder(node.left) + [node.key] + self.__inorder(node.right)

    def __postorder(self, node):
        if node is None:
            return []
        return self.__postorder(node.left) + self.__postorder(node.right) + [node.key]

    def preorder(self):
        return self.__preorder(self.root)

    def inorder(self):
        return self.__inorder(self.root)

    def postorder(self):
        return self.__postorder(self.root)

    def get_minimum(self, node):
        target = node
        while target.has_left():
            target = target.left
        return target

    def get_successor(self, node):
        target = node
        if target.has_right():
            return self.get_minimum(target.right)
        else:
            while target.has_parent():
                if target.parent.left is target:
                    return target.parent
                target = target.parent
            return None

    def delete(self, key):
        node = self.find(key)
        if node is None:
            raise ValueError
        if node.num_children() == 2:
            denode = self.get_successor(node)
        else:
            denode = node
        # denodeは片方にしかない
        if denode.has_left():
            child = denode.left
        else:
            child = denode.right

        # denodeの下から上への参照
        if child is not None:
            child.parent = denode.parent

        # denodeの上から下への参照
        if denode.is_root():
            self.root = denode
        elif denode.parent.left == denode:
            denode.parent.left = child
        else:
            denode.parent.right = child

        if denode is not node:
            node.key = denode.key
        del denode

def main():
    n = int(input())
    tree = Tree()
    for _ in range(n):
        operation = input()
        if operation[0] == "i":
            tree.insert(int(operation.split()[1]))
        elif operation[0] == "f":
            if tree.find(int(operation.split()[1])) is None:
                print("no")
            else:
                print("yes")
        elif operation[0] == "d":
            tree.delete(int(operation.split()[1]))
        else:
            print(" {}".format(" ".join(map(str, tree.inorder()))))
            print(" {}".format(" ".join(map(str, tree.preorder()))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def insert(tree,node):
    parent=None
    child=root
    while child is not None:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    if node<parent:tree[parent][0]=node
    else:tree[parent][1]=node


def In_order(node):
    if node is None:return
    In_order(tree[node][0])
    print(" {}".format(node), end="")
    In_order(tree[node][1])


def Pre_order(node):
    if node is None:return
    print(" {}".format(node), end="")
    Pre_order(tree[node][0])
    Pre_order(tree[node][1])


def find(x,key):
    while x is not None and key!=x:
        if key<x:x=tree[x][0]
        else:x=tree[x][1]
    return x


def parent_search(tree,node):
    parent=None
    child=root
    while child is not None and child!=node:
        parent=child
        if node<child:child=tree[parent][0]
        else:child=tree[parent][1]
    return parent


def getMinimum(node):
    while tree[node][0] is not None:
        node=tree[node][0]
    return node


def getSuccessor(node):
    if tree[node][1] is not None:
        return getMinimum(tree[node][1])
    target=parent_search(tree,node)
    while target is not None and node==tree[target][1]:
        node=target
        target=parent_search(tree,target)
    return target


def delete(tree,node):
    if tree[node][0] is None or tree[node][1] is None:target=node
    else:target=getSuccessor(node)

    if tree[target][0] is not None:child=tree[target][0]
    else:child=tree[target][1]

    child_parent=parent_search(tree,target)
    if target==tree[child_parent][0]:tree[child_parent][0]=child
    else:tree[child_parent][1]=child
    if target==node:
        del tree[node]
        return

    node_parent=parent_search(tree,node)
    if node==tree[node_parent][0]:tree[node_parent][0]=target
    else:tree[node_parent][1]=target
    tree[target]=tree[node]
    del tree[node]


n=int(input())
tree,root={},None
for i in range(n):
    order=input().split()
    if order[0]=="print":
        In_order(root);print()
        Pre_order(root);print()
    elif order[0]=="find":
        if find(root,int(order[1])) is not None:print("yes")
        else:print("no")
    elif order[0]=="delete":
        delete(tree,int(order[1]))
    elif order[0]=="insert":
        num=int(order[1])
        if root is None:
            root=num
            tree[root]=[None,None]
        else:
            tree[num]=[None,None]
            insert(tree,num)

Submission status: Accepted

Solution code:


class Node:
    def __init__(self, key):
        self.parent = None
        self.right = None
        self.left = None
        self.key = key

def insert(root, z):
    y = None
    x = None
    if root != None:
        x = root
        
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
            
    z.parent = y
    if y == None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x
    
def delete(root, z):
    if z.left == None or z.right == None:
        y = z
    else:
        y = getSuccessor(z)
    
    if y.left != None:
        x = y.left
    else:
        x = y.right
        
    if x != None:
        x.parent = y.parent
    
    if y.parent == None:
        root = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x
    
    if y != z:
        z.key = y.key

def getSuccessor(x):
    if x.right != None:
        return getMinimum(x.right)
    y = x.parent
    while y != None and x == y.right:
        x = y
        y = y.parent
    return y

def getMinimum(x):
    while x.left != None:
        x = x.left
    return x
    
def printInOrder(z):
    if z == None:
        return
    if z.left != None:
        printInOrder(z.left)
    inorder.append(str(z.key))
    #print(z.key, end = " ")
    if z.right != None:
        printInOrder(z.right)
        
def printPreOrder(z):
    if z == None:
        return
    #print(z.key, end = " ")
    preorder.append(str(z.key))
    if z.left != None:
        printPreOrder(z.left)
    if z.right != None:
        printPreOrder(z.right)

root = None


n = int(input())
for i in range(n):
    command = input()
    if command[0] == "i":
        com,num = command.split()
        z = Node(int(num))
        insert(root, z)
        if root == None:
            root = z
    elif command[0] == "f":
        com,num = command.split()
        z = Node(int(num))
        x = find(root, int(z.key))
        if x != None:
            print("yes")
        else:
            print("no")
    
    elif command[0] =="d":
        com,num = command.split()
        z = Node(int(num))
        delete(root, find(root, int(z.key)))
    

    else:
        inorder = []
        printInOrder(root)
        print(" ", end = "")
        print(' '.join(inorder))
        preorder = []
        printPreOrder(root)
        print(" ", end = "")
        print(' '.join(preorder))