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

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                    self.left.parent = self
                else:
                    self.left.insert(data)

            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                    self.right.parent = self
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def delete(self, data):
        if self.data:
            if data < self.data:
                self.left.delete(data)
            elif data > self.data:
                self.right.delete(data)
            else:
                if self.left == None and self.right == None:  #Blatt
                    if self.parent.left.data == data:
                        self.parent.left = None
                    else:
                        self.parent.right = None
                elif self.left == None or self.right == None:  #1 kind
                    if self.left == None:
                        self.data = self.right.data
                        self.right = self.right.right
                    else:
                        self.data = self.left.data
                        self.left = self.left.left
                else:  # 2 Dreckskinder
                    right_min = self.right
                    while not right_min.left is None:
                        right_min = right_min.left
                    self.data = right_min.data
                    right_min.delete(right_min.data)

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()


class Tree:
    def __init__(self):
        self.root = Node()

    def insert(self, data):
        self.root.insert(data)

    def delete(self, data):
        self.root.delete(data)

    def left_rotate(self, x):
        y = x.right
        if x:
            y.parent = x.parent
            if y.parent is None:
                self.root = y
            else:
                if y.parent.left is x:
                    y.parent.left = y
                elif y.parent.right is x:
                    y.parent.right = y
            x.right = y.left
            if x.right is not None:
                x.right.parent = x
            y.left = x
            x.parent = y

    def right_rotate(self, x):
        y = x.left
        if y:
            y.parent = x.parent
            if y.parent is None:
                self.root = y
            else:
                if y.parent.left is x:
                    y.parent.left = y
                elif y.parent.right is x:
                    y.parent.right = y
            x.left = y.right
            if x.left is not None:
                x.left.parent = x
            y.right = x
            x.parent = y

    def double_left_rotation(self, x):
        self.right_rotate(x)
        self.left_rotate(x.left)

    def double_right_rotation(self, x):
        self.left_rotate(x)
        self.right_rotate(x.right)

    def printTree(self):
        self.root.printTree()


tree = Tree()
tree.insert(42)
tree.insert(16)
tree.insert(25)
tree.insert(58)
tree.insert(49)
tree.insert(60)
tree.insert(8)

tree.printTree()