#!/bin/env python3


class NODE_COLOR:

    RED = 0
    BLACK = 1


class Node(object):


    def __init__(self,value):
        self.value = value
        self.color = NODE_COLOR.BLACK
        self.parent = None

        self.left = None
        self.right = None


class RBTree(object):

    def __init__(self, *nodes):
        self.root = nodes[0]

        for node in nodes[1:]:
            self.insert(node)

    """
    wrapper used for API
    """
    def find(self,node):
        return self.__find(node,self.root)


    """
    Searches for a node in the tree
    returns the node if it exists, or None othewise
    Impements binary search
    """
    def __find(self, node, root):
        if node is root or root is None:
            return root

        if node.value > root.value:
            return self.__find(node,root.right)
        else:
            return self.__find(node,root.left)

    def min(slef,root):
        if root.left:
            return self.min(root.left)
        else:
            return root

    def max(self,root):
        if root.right:
            return self.max(root.right)
        else:
            return root

    def remove(self,node):
         node = self.find(node,self.root)

         if node:
             if node.right and node.left:
                min_child = self.min(node.right)
                node = min_child
             elif node.right:
                node = node.right
             elif node.left:
                node = node.left
             else:
                node = None

    def insert(self,node):
        self.__insert(node,self.root)


    def __insert(self,node,root, prev = None):
        if root is None:
            root = node
            if prev:
                root.parent = prev
                if root.value >= prev.value:
                    prev.right = root
                else:
                    prev.left = root
            else:
                self.root = root
        elif node.value >= root.value:
            return self.__insert(node,root.right,root)
        else:
            return self.__insert(node,root.left,root)

    def left_rotate(self,node):
        tmp = node.right

        node.right.left.parent = node
        node.right = node.right.left

        if node.parent:
            tmp.parent = node.parent
            if node.parent.right is node:
                node.parent.right = tmp
            else:
                node.parent.left = tmp
        else:
            self.root = tmp

        node.parent = tmp
        tmp.left = node

    def right_rotate(self,node):
        tmp = node.left

        node.left.right.parent = node
        node.left = node.left.right

        if node.parent:
            tmp.parent = node.parent
            if node.parent.right is node:
                node.parent.right = tmp
            else:
                node.parent.left = tmp
        else:
            self.root = tmp

        node.parent = tmp
        tmp.right = node


    def show(self):
        self.in_order(self.root)

    def in_order(self,root):
        if root.left:
            self.in_order(root.left)
        print(root.value)
        if root.right:
            self.in_order(root.right)








if __name__ == "__main__":
        nodes = [Node(15),Node(6),Node(20),Node(9),Node(3),Node(19),Node(45)]
        tree = RBTree(*nodes)

        tree.right_rotate(nodes[0])
        tree.show()