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:
class BinarySearchTree:
    def __init__(self):
        self.lcs = {}
        self.rcs = {}
        self.preorder = []
        self.inorder = []
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = key
            self.lcs[key] = None
            self.rcs[key] = None
            return
        parent = self.root
        while True:
            if key < parent:
                if self.lcs[parent] is None:
                    self.lcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.lcs[parent]
            else:
                if self.rcs[parent] is None:
                    self.rcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.rcs[parent]

    def _find(self, key, cur):
        if key == cur:
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._find(key, self.lcs[cur])
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._find(key, self.rcs[cur])

    def find(self, key):
        return self._find(key, self.root)

    def _search(self, cur):
        self.preorder.append(cur)
        if self.lcs[cur]:
            self._search(self.lcs[cur])
        self.inorder.append(cur)
        if self.rcs[cur]:
            self._search(self.rcs[cur])

    def print(self):
        self.preorder = []
        self.inorder = []
        self._search(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))

    def _delete(self, key, cur, parent):
        if key == cur:
            if self.lcs[cur] is None:
                # print('R', key)
                if self.lcs[parent] == cur:
                    self.lcs[parent] = self.rcs[cur]
                else:
                    self.rcs[parent] = self.rcs[cur]
            elif self.rcs[cur] is None:
                # print('L', key)
                if self.lcs[parent] == cur:
                    self.lcs[parent] = self.lcs[cur]
                else:
                    self.rcs[parent] = self.lcs[cur]
            else:
                # print('B', key)
                n = self.inorder[self.inorder.index(key) + 1]
                self._delete(n, cur, parent)
                self.lcs[n], self.rcs[n] = self.lcs[cur], self.rcs[cur]
                self.lcs[cur], self.rcs[cur] = None, None
                if key == self.root:
                    self.root = n
                elif self.lcs[parent] == cur:
                    self.lcs[parent] = n
                else:
                    self.rcs[parent] = n
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._delete(key, self.lcs[cur], cur)
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._delete(key, self.rcs[cur], cur)

    def delete(self, key):
        self.preorder = []
        self.inorder = []
        self._search(self.root)
        self._delete(key, self.root, None)


T = BinarySearchTree()
N = int(input())
for _ in range(N):
    s = input().split()
    if s[0] == 'insert':
        T.insert(int(s[1]))
    elif s[0] == 'find':
        print('yes' if T.find(int(s[1])) else 'no')
    elif s[0] == 'delete':
        T.delete(int(s[1]))
    else:
        T.print()

Submission status: Accepted

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

class Tree:
    def __init__(self):
        self.root = None
        self.list = []
    
    def insert(self, node_tobe_added):
            y = None #「xの親」って書いてあるけど、「zの親」では？
            x = self.root
            while x != None:
                #ここで親を設定する。xを一つずつ葉に進めて、yに代入する。yがｚの親になる。
                y = x
                if node_tobe_added.key < x.key:
                    x = x.left
                else:
                    x = x.right
            #ここでyがzの親に設定される。
            node_tobe_added.parent = y 
            
            #yがNoneなら何もないということなのでzがrootになる。
            if y == None:
                self.root = node_tobe_added
            elif node_tobe_added.key < y.key:
                #node_tobe_addedをyの左の子にする
                y.left = node_tobe_added
            else:
                #node_tobe_addedをyの右の子にする
                y.right = node_tobe_added
                
    def find(self, key):
        x = self.root
        while x != None and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x
    
    def delete(self, node):
        if node.left == None or node.right == None:
            y = node
        else:
            y = self.get_successor(node)
        
        if y.left != None:
            x = y.left
        else:
            x = y.right
        
        if x != None:#nodeの子がいた場合は、子をnodeの親とつなげる。
            x.parent = y.parent
        
        if y.parent == None:#yがrootのときは、xをrootにする。
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        if y != node:
            node.key = y.key
        
    def get_successor(self, node):
        if node.right != None:
            return self.get_minimum(node.right)
        
        y = node.parent
        while y != None and node == y.right:
            node = y
            y = y.parent
        return y
    
    def get_minimum(self, node):
        while node.left != None:
            node = node.left
        return node
    
    def pre_parse(self, node):
        if node == None:
            return
        self.list.append(node.key)
        self.pre_parse(node.left)
        self.pre_parse(node.right)
    
    def in_parse(self, node):
        if node == None:
            return
        self.in_parse(node.left)
        self.list.append(node.key)
        self.in_parse(node.right)

T = Tree()

N = int(input())
for i in range(N):
        order, *key = input().split() #printの場合はkeyがないので、*をつけて配列として扱う。
        if order == "print":
            T.list = []
            T.in_parse(T.root)
            print(" " + " ".join(map(str, T.list)))
            T.list = []
            T.pre_parse(T.root)
            print(" " + " ".join(map(str, T.list)))
        elif order == "insert":
            T.insert(Node(int(key[0]))) #なぜかわからないがintにしないとWAになる。
        elif order == "find":
            if T.find(int(key[0])):
                print("yes")
            else:
                print("no")
        else:
            node = T.find(int(key[0]))
            T.delete(node)

Submission status: Accepted

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

class BinaryTree():
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            parentnode = curnode = self.root
            while curnode != None:
                parentnode = curnode
                if curnode.value > value:
                    curnode = curnode.left
                else:
                    curnode = curnode.right
            if value > parentnode.value:
                parentnode.right = Node(value)
            else:
                parentnode.left = Node(value)

    def find(self, value):
        c, _ = self.findvalue(value)
        if c is None:
            return False
        else:
            return True

    def findvalue(self, value):
        parentnode = curnode = self.root
        while curnode != None:
            if value == curnode.value:
                return curnode, parentnode
            parentnode = curnode
            if value > curnode.value:
                curnode = curnode.right
            else:
                curnode = curnode.left
        return None, None
    
    def replace_child(self, parentnode, childnode, newnode):
        if parentnode == self.root:
            self.root = newnode
        elif parentnode.value > childnode.value:
            parentnode.left = newnode
        else:
            parentnode.right = newnode
    
    def delete(self, value):
        curnode, parentnode = self.findvalue(value)
        if curnode is None:
            return False
        if curnode.left == None and curnode.right == None:
            self.replace_child(parentnode, curnode, None)
        elif curnode.right == None:
            self.replace_child(parentnode, curnode, curnode.left)
        elif curnode.left == None:
            self.replace_child(parentnode, curnode, curnode.right)
        else:
            p = curnode
            r = curnode.right
            while r.left != None:
                p = r
                r = r.left
            curnode.value = r.value
            self.replace_child(p, r, r.right)


    def preorder(self, root):
        if root == None:
            pass
        else:
            print(' %d' % root.value, end='')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root == None:
            pass
        else:
            self.inorder(root.left)
            print(' %d' % root.value, end='')
            self.inorder(root.right)

if __name__ == '__main__':
    n = int(input())
    binarytree = BinaryTree()
    for _ in range(n):
        common = input()
        if common[0] == 'i':
            binarytree.insert(int(common[7:]))
        elif common[0] == 'f':
            if binarytree.find(int(common[5:])):
                print('yes')
            else:
                print('no')
        elif common[0] == 'd':
            binarytree.delete(int(common[7:]))
        else:
            binarytree.inorder(binarytree.root)
            print()
            binarytree.preorder(binarytree.root)
            print()

Submission status: Accepted

Solution code:

class Node:
    key = None
    parent = None
    left = None
    right = None

    def __init__(self, key):
        self.key = key


def insert(key):
    global T
    global root

    new_node = Node(key)
    T.append(new_node)

    if root is None:
        root = new_node

    else:
        y = None  # 親
        x = root  # 子

        while x is not None:
            y = x
            if key < x.key:
                x = x.left
            else:
                x = x.right

        new_node.parent = y
        if new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node


def find(key):
    global T
    global root

    x = root

    while x is not None and key != x.key:
        # print(key, x.key)

        if key < x.key:
            x = x.left
        else:
            x = x.right
    return x  # マッチしなければNONEが戻る。


def delete(key):
    global T
    global root

    z = find(key)


    # まず、削除するノードを決める。
    if z.left is None or z.right is None:
        y = z
    else:
        y = tree_successor(z)

    # yの子xを決める。
    if y.left is not None:
        x = y.left  # 親がいなくなる子ノード
    else:
        x = y.right

    if x is not None:
        x.parent = y.parent  # yの親が新しいxの親になる

    if y.parent is None:
        root = x  # yに親がいない場合は、つまりyがルートなので、xが新しいルートになる。
    else:
        if y == y.parent.left:
            y.parent.left = x  # yの親の方の子供をxに更新する。
        else:
            y.parent.right = x

    if y != z:
        z.key = y.key


def tree_minimum(x):
    """ xを根とした場合に、一番小さなノードを見つける（＝左下に行き続ける） """
    while x.left is not None:
        x = x.left
    return x


def tree_successor(x):
    """ 中間巡回でxの次に来るものを見つける。
        中間巡回は昇順ソートと同じなので、つまり、
        xの次に大きいノードを探すということ。

        もしxに右の子がいれば、x以下の木のなかで、
        xの次に大きいノードを見つけることができる。

        しかし、もしxが右の子を持たなければ、
        全体の木の中で次に大きいのは、
        xより上の木まで探しに行く必要がある。
    """

    """ xに右の子がいる場合 """
    if x.right is not None:
        return tree_minimum(x.right)

    """ xに右の子がいない場合 """
    y = x.parent  # xが親の左側の子の場合は、これで完了。

    # 右側の子だった場合は、弟の立場になるまで遡る。
    while y is not None and x == y.right:
        x = y
        y = y.parent

    return y


def in_order(node, order):
    if node is None:
        return

    in_order(node.left, order)
    order.append(node.key)
    in_order(node.right, order)


def pre_order(node, order):
    if node is None:
        return

    order.append(node.key)
    pre_order(node.left, order)
    pre_order(node.right, order)


m = int(input())
T = []
root = None

for i in range(m):
    order = input()

    if order.startswith('print'):
        output = []
        in_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

        output = []
        pre_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

    elif order.startswith('find'):
        order, value = order.split()
        value = int(value)
        _ = find(value)
        if _ is None:
            print('no')
        else:
            print('yes')

    elif order.startswith('delete'):
        order, value = order.split()
        value = int(value)
        delete(value)

    else:
        order, value = order.split()
        value = int(value)
        insert(value)

Submission status: Accepted

Solution code:
import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            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 and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        return x
    def delete(self, key):
        z = self.find(key)
        y = self.successor(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == None:
            self.root = x 
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key
    def successor(self, x):
        if x.right:
            return self.minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def minimum(self, x):
        while x.left:
            x = x.left
        return x
    
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    elif line[0] == 'f':
        print('yes' if tree.find(int(line.split()[1])) else 'no')
    elif line[0] == 'd':
        tree.delete(int(line.split()[1]))            
    else:
        tree.print()

Submission status: Accepted

Solution code:
class node:
    def __init__(self, key):
        self.k = key
        self.p = None
        self.l = None
        self.r = None

def preParse(u):
    if u == None:
        return
    print(" " + str(u.k), end = '')
    preParse(u.l)
    preParse(u.r)

def inParse(u):
    if u == None:
        return
    inParse(u.l)
    print(" " + str(u.k), end = '')
    inParse(u.r)

def postParse(u):
    if u == None:
        return
    postParse(u.l)
    postParse(u.r)
    print(" " + str(u.k), end = '')

root = None
def insert(k):
    global root
    parent = None
    u = root
    z = node(k)
    while u != None:
        parent = u
        if z.k < u.k:
            u = u.l
        else:
            u = u.r

    z.p = parent
    if parent == None:
        root = z
    elif z.k < parent.k:
        parent.l = z
    else:
        parent.r = z

def find(k):
    global root
    u = root
    while u != None and u.k != k:
        if k < u.k:
            u = u.l
        else:
            u = u.r
    return u

def delete (k):
    global root
    u = find(k)
    if u.l == None or u.r == None:
        y = u
    else:
        y = getSuccessor(u)

    if y.l != None:
        x = y.l
    else:
        x = y.r

    if x != None:
        x.p = y.p

    if y.p == None:
        root = x
    elif y == y.p.l:
        y.p.l = x
    else:
        y.p.r = x

    if y != u:
        u.k = y.k

def getSuccessor(z):
    if z.r != None:
        return getMinimum(z.r)
    
    y = z.p
    while y != None and z == y.r:
        z = y
        y = y.p
    return y

def getMinimum(z):
    while z.l != None:
        z = z.l
    return z

n = int(input())
cmdList = [input() for _ in range(n)]

for cmd in cmdList:
    if cmd[0] == "p":
        inParse(root)
        print("")
        preParse(root)
        print("")
    elif cmd[0] == "f":
        print("no" if find(int(cmd[5:])) == None else "yes")
    elif cmd[0] == "d":
        a = 1
        delete(int(cmd[7:]))
    else:
        insert(int(cmd[7:]))

Submission status: Accepted

Solution code:
class Node():
    """節クラス: valは節の値, parent/left/rightはそれぞれ親/左側の子/右側の子へのポインタを表す"""
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.right = None
        self.left = None


class BinaryTree():
    def __init__(self):
        self.root = None

    def search(self, val: int) -> bool:
        """二分木に値valを持つ節が存在するかどうか判定する
        根から順番に子を辿っていき、valと一致する節が存在する場合はTrue、存在しない場合はFalseを返す
        """
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False 

    def insert(self, val: int):
        """二分木に値valを持つ節を追加する（すでに二分木内に同じ要素が存在している場合も追加する）
        根から順番に子を辿っていき、ポインタが示す先に節が存在しなくなったらNode(val)として節を追加する
        """
        if self.root is None:
            # 二分木の根が存在しないときはrootに節を作る
            self.root = Node(val)
            return

        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.left = Node(val)
                    ptr.left.parent = ptr
                    return
                ptr = ptr.left
            else:
                if ptr.right is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.right = Node(val)
                    ptr.right.parent = ptr
                    return
                ptr = ptr.right
        
    def delete(self, val: int):
        """二分木から値valを持つ節を削除する
        根から順番に子を辿っていき、ptr.val == val が見つかったらptrをつなぎ替える。
        """
        if self.root is None:
            # 二分木の根に節が存在しないときは何もしない
            return 
        
        ptr = self.root
        # ptr.val == valとなる節を探す             
        while True: 
            if ptr is None:
                return
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
       
        # 子が存在しないとき
        if ptr.left is None and ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None
        # 子が右側にのみ存在するとき
        elif ptr.left is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.right
                ptr.right.parent = ptr.parent
            else:
                ptr.parent.right = ptr.right
                ptr.right.parent = ptr.parent
        # 子が左側にのみ存在するとき
        elif ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.left
                ptr.left.parent = ptr.parent
            else:
                ptr.parent.right = ptr.left
                ptr.left.parent = ptr.parent
        # 子が両側にのみ存在するとき
        else:
            s = self.search_min(ptr.right)
            ptr.val = s.val
            if s.parent.left == s:
                s.parent.left = None
            else:
                s.parent.right = None            
    
    def search_min(self, ptr):
        """ptrを部分木の根としたときのptrの最小値の節へのポインタを返す
        ptr.leftをひたすら辿っていくことで可能"""
        while True:
            if ptr.left is None:
                return ptr
            ptr = ptr.left
            
    def rotate_left(self, ptr):
        """木を左回転する"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

 
    def rotate_right(self, ptr):
        """木を右回転する"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def preorder_tree_walk(self, ptr, res):
        """先行順巡回(preorder tree walk)"""
        if ptr is None:
            return res
        res.append(ptr.val)
        if ptr.left is not None:
            self.preorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.preorder_tree_walk(ptr.right, res)
        return res

    def inorder_tree_walk(self, ptr, res):
        """中間順巡回(inorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        res.append(ptr.val)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        return res

    def postorder_tree_walk(self, ptr, res):
        """後行順巡回(postorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        res.append(ptr.val)
        return res
      
      
n = int(input())
info = [list(input().split()) for i in range(n)]
bt = BinaryTree()

for i in range(n):
    if info[i][0] == "insert":
        if bt.search(int(info[i][1])):
            continue
        else:
            bt.insert(int(info[i][1]))
    elif info[i][0] == "find":
        if bt.search(int(info[i][1])):
            print("yes")
        else:
            print("no")
    elif info[i][0] == "delete":
        bt.delete(int(info[i][1]))
    else:
        print(" ", end="")
        print(*bt.inorder_tree_walk(bt.root, res=[]))
        print(" ", end="")
        print(*bt.preorder_tree_walk(bt.root, res=[]))