class Tree(object):

    def __init__(self):
        self.root = None
        self.size = 0

    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        else:
            self.root = Node(key, val)
        self.size += 1

    def get(self, key):
        res = self._get(key, self.root)
        if res:
            return res.val
        return None

    def delete(self, key):
        if len(self) > 1:
            node_to_delete = self._get(key, self.root)
            if not node_to_delete:
                raise KeyError('key not in tree')
            else:
                self._delete(node_to_delete)
                self.size -= 1
        elif len(self) == 1 and self.root.key == key:
            self.root = None
            self.size = 0
        else:
            raise KeyError('key not in tree')

    def _put(self, key, val, curr_node):
        if key < curr_node.key:
            if curr_node.left:
                self._put(key, val, curr_node.left)
            else:
                curr_node.left = Node(key, val, parent=curr_node)
        else:
            if curr_node.right:
                self._put(key, val, curr_node.right)
            else:
                curr_node.right = Node(key, val, parent=curr_node)

    def _get(self, key, curr_node):
        if not curr_node:
            return None
        if key == curr_node.key:
            return curr_node
        if key < curr_node.key:
            return self._get(key, curr_node.left)
        return self._get(key, curr_node.right)

    def _delete(self, node):
        if node.is_leaf():
            if node.is_left():
                node.parent.left = None
            else:
                node.parent.right = None
        elif node.has_both_children():
            succ = node.find_succerror()
            succ.splice_out()
            node.key = succ.key
            node.val = succ.val
        else:
            if node.left:
                if node.is_left():
                    node.left.parent = node.parent
                    node.parent.left = node.left
                elif node.is_right():
                    node.left.parent = node.parent
                    node.parent.right = node.left
                else:
                    node.replace(node.left.key, node.left.val, node.left.left, node.left.right)
            else:
                if node.is_left():
                    node.right.parent = node.parent
                    node.parent.left = node.right
                elif node.is_right():
                    node.right.parent = node.parent
                    node.parent.right = node.right
                else:
                    node.replace(node.right.key, node.right.val, node.right.left, node.right.right)

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def __repr__(self):
        return self.root.__repr__()

    def __setitem__(self, key, val):
        self.put(key, val)

    def __getitem__(self, key):
        return self.get(key)

    def __delitem__(self, key):
        self.delete(key)

    def __contains__(self, key):
        return bool(self.get(key))


class Node(object):

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

    def is_left(self):
        """
        >>> p = Node('a', 1)
        >>> n = Node('b', 2, parent=p)
        >>> p.left = n
        >>> assert n.is_left()
        """
        return self.parent is not None and self.parent.left is self

    def is_right(self):
        """
        >>> p = Node('a', 1)
        >>> n = Node('b', 2, parent=p)
        >>> p.right = n
        >>> assert n.is_right()
        """
        return self.parent is not None and self.parent.right is self

    def is_root(self):
        """
        >>> p = Node('a', 1)
        >>> n = Node('b', 2, parent=p)
        >>> p.right = n
        >>> assert p.is_root()
        >>> assert not n.is_root()
        """
        return self.parent is None

    def is_leaf(self):
        """
        >>> p = Node('a', 1)
        >>> n = Node('b', 2, parent=p)
        >>> p.right = n
        >>> assert not p.is_leaf()
        >>> assert n.is_leaf()
        """
        return self.left is None and self.right is None

    def has_any_children(self):
        """
        >>> p = Node('a', 1)
        >>> n = Node('b', 2, parent=p)
        >>> p.right = n
        >>> assert p.has_any_children()
        """
        return self.left is not None or self.right is not None

    def has_both_children(self):
        """
        >>> p = Node('a', 1)
        >>> n1 = Node('b', 2, parent=p)
        >>> p.right = n1
        >>> n2 = Node('c', 3, parent=p)
        >>> p.left = n2
        >>> assert p.has_any_children()
        >>> assert p.has_both_children()
        """
        return self.left is not None and self.right is not None

    def replace(self, key, val, left, right):
        self.key = key
        self.val = val
        self.left = left
        self.right = right
        if self.left:
            self.left.parent = self
        if self.right:
            self.right.parent = self

    def find_succerror(self):
        succ = None
        if self.right:
            succ = self.right.find_min()
        else:
            if self.parent:
                if self.is_left():
                    succ = self.parent
                else:
                    self.parent.right = None
                    succ = self.parent.find_succerror()
                    self.parent.right = self
        return succ

    def find_min(self):
        res = self
        while res.left:
            res = res.left
        return res

    def splice_out(self):
        if self.is_leaf():
            if self.is_left():
                self.parent.left = None
            else:
                self.parent.right = None
        else:
            if self.left:
                if self.is_left():
                    self.parent.left = self.left
                else:
                    self.parent.right = self.left
                self.left.parent = self.parent
            else:
                if self.is_leaf():
                    self.parent.left = self.right
                else:
                    self.parent.right = self.right
                self.right.parent = self.parent

    def __iter__(self):
        if self:
            if self.left:
                for ele in self.left:
                    yield ele
            yield self.key
            if self.right:
                for ele in self.right:
                    yield ele

    def __repr__(self):
        return '{} --> {}:{} <-- {}'.format(self.left, self.key, self.val, self.right)


def main():
    t = Tree()
    print t[3]

    t[5] = 'e'
    print len(t)
    print t

    t[4] = 'd'
    print len(t)
    print t

    t[6] = 'f'
    print len(t)
    print t

    t[3] = 'c'
    print len(t)
    print t

    print t[3]
    print t[4]
    print t[5]
    print t[6]
    print t[7]

    print 7 in t
    print 6 in t

    for ele in t:
        print ele


def test_delete_leaf():
    print 'test delete leaf'
    t = Tree()
    t[2] = 'b'
    t[1] = 'a'
    t[3] = 'c'
    print t
    del t[1]
    print t
    del t[3]
    print t


def test_delete_root():
    print 'test delete root'
    t = Tree()
    print t
    t[2] = 'b'
    print t
    del t[2]
    print t


def test_delete_half():
    print 'test delete half'
    t = Tree()

    t[3] = 'c'
    t[2] = 'b'
    t[1] = 'a'
    del t[2]
    print t

    t = Tree()
    t[3] = 'c'
    t[1] = 'a'
    t[2] = 'b'
    del t[1]
    print t

    t = Tree()
    t[1] = 'a'
    t[2] = 'b'
    t[3] = 'c'
    del t[2]
    print t

    t = Tree()
    t[1] = 'a'
    t[3] = 'c'
    t[2] = 'b'
    del t[3]
    print t

    t = Tree()
    t[2] = 'b'
    t[1] = 'a'
    del t[2]
    print t

    t = Tree()
    t[2] = 'b'
    t[3] = 'c'
    del t[2]
    print t


def test_delete_full():
    print 'test delete full'
    t = Tree()
    t[4] = 'd'
    t[2] = 'b'
    t[1] = 'a'
    t[3] = 'c'
    print t

    del t[3]
    print t

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()
    test_delete_leaf()
    test_delete_root()
    test_delete_half()
    test_delete_full()