from typing import List


class BinSearchTree(dict):
    def __init__(self, tree_dict: dict):
        self.tree: dict = tree_dict
        self.parent = None
        if tree_dict in ({float("+inf"): {}}, {float("-inf"): {}}):
            self._leaf_init()
        else:
            left, right = list(tree_dict.values())[0].items()
            if self.is_leaf(left) and self.is_leaf(right):
                self._empty_node_init()
            else:
                self._subtree_init()

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

    def is_leaf(self, tree_dict=None):
        if tree_dict is None:
            tree_dict = self.tree
        if tree_dict in ({float("+inf"): {}}, {float("-inf"): {}}) or \
            (
            isinstance(tree_dict, type(self)) and\
            tree_dict.value == [] and\
            tree_dict.children == [] and\
            tree_dict.level == 1):
            return True
        return False

    def is_empty_node(self, tree_dict=None):
        if self.is_leaf(): return False
        if tree_dict is None:
            tree_dict = self.tree
        value = list(tree_dict.keys())[0]  # только 1 элемент
        left, right = tree_dict[value].items()
        left = {left[0]: left[1]}
        right = {right[0]: right[1]}
        return value is not None and \
            (
                all([
                left == {float("-inf"): {}},
                right == {float("+inf"): {}}])
                or \
                (
                    isinstance(tree_dict, type(self)) and\
                    tree_dict.value == list(tree_dict.keys()) and\
                    tree_dict.children == [AATree({}), AATree({})] and\
                    tree_dict.level == 1

                )
            )

    def _leaf_init(self):
        self.value: list = []
        self.children: list = []
        self.level: int = 1
        if self.parent is not None and self is self.parent.right:
            self.tree = {float("+inf"): {}}
        else:
            self.tree = {float("-inf"): {}}

    def _empty_node_init(self):
        tree_dict = self.tree
        self.value: list = list(tree_dict.keys())
        self.children: list = [AATree({}), AATree({})]
        self.left, self.right = self.children
        self.level: int = 1
        self.left.parent = self
        self.right.parent = self
        self.tree = {self.value: {
            None: {},
            None: {}
        }}

    def _subtree_init(self):
        tree_dict = self.tree
        Node = type(self)
        self.value: list = list(tree_dict.keys())  # 1 element
        left, right = tree_dict[self.value[0]].items()
        left = {left[0]: left[1]}
        right = {right[0]: right[1]}
        self.children: List[Node] = [Node(left), Node(right)]
        self.left, self.right = self.children
        self.level: int = min([self.left.level, self.right.level]) + 1
        self.left.parent = self
        self.right.parent = self
        self.left.tree = left
        self.right.tree = right

    def get(self, value):
        if self.value == [value]:
            return self
        elif self.is_leaf() or self.is_empty_node():
            raise ValueError("tree has no such value in it")
        elif value < self.value[0]:
            return self.left.get(value)
        elif value > self.value[0]:
            return self.right.get(value)

    def min(self):
        if self.is_leaf(): return float("+inf")
        elif self.left.is_leaf():
            return self
        else:
            return self.left.min()

    def max(self):
        if self.is_leaf(): return float("-inf")
        elif self.right.is_leaf():
            return self
        else:
            return self.right.max()

    def next(self):
        try:
            if not self.right.is_leaf():
                return self.right.min()
            parent = self.parent
            while not parent.is_leaf() and self == parent.right:
                self = parent
                parent = parent.parent
            return parent
        finally:
            self._fix_level()

    def prev(self):
        try:
            if not self.left.is_leaf:
                return self.left.max()
            parent = self.parent
            while not parent is None and self == parent.left:
                self = parent
                parent = parent.parent
            return parent
        finally:
            self._fix_level()

    def insert(self, value: int):
        Node = type(self)
        if self.is_leaf(self):
            self = Node({value: {None: {}, None: {}}})
        elif value < self.value:
            self.left.insert(value)
        elif value > self.value:
            self.right.insert(value)
        self._fix_level()

    def delete(self, value):
        Node = type(self)
        if self.is_leaf(self):
            pass
        if value < self.value:
            self.left.delete(value)
        elif value > self.value:
            value.right.delete(value)
        elif not (value.left.is_leaf() or self.right.is_leaf()):
            self.value = self.min().value
            self.tree = {self.value: list(self.tree.values())[0]}
            self.right.delete(self.value)
        else:
            if not self.left.is_leaf():
                self = self.left
            elif not self.right.is_leaf():
                self = self.right
            else:
                self = Node({})
        self._fix_level()

    def _root_lvl_from_leaf(self):
        if self.is_leaf:
            self.level = 1
        if not self.parent is None:
            parent = self.parent
            left = parent.left
            parent.level = left.level + 1
            parent._fix_level(self)
        if self.parent is None:
            return self.level

    def _min_lvl_from_root_unfixed(self, root_lvl) -> int:
        if self.is_leaf():
            return 1
        left, right = self.children
        left.level = root_lvl - 1
        right.level = root_lvl - 1
        if right.is_leaf():
            min_left_lvl = left._min_lvl_from_root_unfixed(left.level)
            return min(min_left_lvl, root_lvl - 1)
        elif left.is_leaf():
            min_right_lvl = right._min_lvl_from_root_unfixed(right.level)
            return min(min_right_lvl, root_lvl - 1)
        else:
            return left._min_lvl_from_root_unfixed(left.level)



    def _add_level(self, lvl2add: int):
        self.level += lvl2add
        if not self.is_leaf():
            self.left._add_level(lvl2add)
            self.right._add_level(lvl2add)

    def _fix_level(self):
        root_lvl = self._root_lvl_from_leaf()
        min_leaf_lvl = self._min_lvl_from_root_unfixed(root_lvl)
        self._add_level(1 - min_leaf_lvl)



class RBTree(BinSearchTree):
    def __init__(self, tree_dict: dict):
        super().__init__(tree_dict)
        if self.is_leaf():
            self.color: bool = False  # False for black, True for red
        else:
            self.color: bool = not min(self.children, key=lambda x: x.value).color

    def next(self):
        try:
            return super().next()
        finally:
            self.__fix_colors()

    def prev(self):
        try:
            super().prev()
        finally:
            self.__fix_colors()

    def insert(self, value: int):
        super().insert(value)
        self.__fix_colors()

    def delete(self, value):
        super().delete(value)
        self.__fix_colors()

    def __fix_colors(self):
        self._fix_level()
        if self.is_leaf(self):
            self.color = False  # black
        else:
            self.color = bool((self.level + 1) % 2)



class AATree(RBTree):
    def __init__(self, tree_dict: dict):
        super().__init__(tree_dict)

    def skew(self):
        # не делаю классметодом потому что
        # метод должен делать взаимодействовать с объектом
        Node = type(self)
        if not self.is_leaf and not self.left.is_leaf():
            self = Node(
                {
                    self.left.value: {
                        **self.left.left,
                        self.value: {
                            **self.left.right,
                            **self.right
                        }
                    }
                }
            )
        self.__fix_colors()

    def split(self):  # tree: AAtree
        if self.is_leaf() or \
           self.right.is_leaf() or \
           self.right.right.is_leaf():
            pass
        elif not any([
            self.is_leaf(),
            self.right.is_leaf(),
            self.right.right.is_leaf()
            ]) and self.level == self.right.right.level:
            self = {
                self.right.value: {
                    self.value: {
                        **self.left,
                        **self.right.left
                    },
                    **self.right.right
                }
            }
        self.__fix_colors()

    def insert(self, value: int):
        Node = type(self)
        if self.is_leaf(self):
            self = Node({value: {}})
        elif value < self.value[0]:
            self.left.insert(value)
        elif value > self.value[0]:
            self.right.insert(value)
        self.skew()
        self.split()
        self.__fix_colors()

    def __decrease_level(self):
        if self.children == []:
            right_level = 1
        else:
            right_level = min(self.children, key = lambda x: x.level).level + 1
        if right_level < self.level:
            self.level = right_level
            if right_level < self.right.level:
                self.right.level = right_level
        self.__fix_colors()

    def delete(self, value: int):
        if not self.is_leaf(self):
            if value > self.value[0]:
                self.right.delete(value)
            elif value < self.value[0]:
                self.right.delete(value)
            elif self.left.is_leaf():
                successor = self.successor()
                right = self.right
                right.delete(successor.value)
                self.value = successor.value
            else:
                predecessor = self.predecessor()
                left = self.left
                left.delete(predecessor.value)
                self.value = predecessor.value
        self.__decrease_level()
        self.skew()
        if not self.is_leaf():
            self.right.skew()
            if not self.right.is_leaf():
                self.right.right.skew()
        self.split()
        if not self.is_leaf():  self.right.split()
        self.__fix_colors()

    def __fix_colors(self):
        if self.is_leaf(self):
            self.color = False  # black
        else:
            self.color = bool((self.level + 1) % 2)



if __name__ == "__main__":
    from pprint import pprint
    dict_example = {
        13: {
            8: {
                1: {
                    float("-inf"): {},
                    6: {
                        float("-inf"): {},
                        float("+inf"): {}
                        }
                    },
                11: {
                    float("-inf"): {},
                    float("+inf"): {}
                    }
                },
            17: {
                15: {
                    float("-inf"): {},
                    float("+inf"): {}
                    },
                25: {
                    22: {
                        float("-inf"): {},
                        float("+inf"): {}
                        },
                    27: {
                        float("-inf"): {},
                        float("+inf"): {}
                        }
                    }
                }
            }
        }
    tree = AATree(dict_example)
    pprint(tree.get(25))
    print(tree.value)



"""
AATree - класс

вывод (__repr__()) - позволяет выводить объект в консоль, например, принтом, выводит карту дерева
is_leaf() - bool метод, возвращает значение в зависимости от того, лист ли дерево (лист - True)
is_empty_node() - bool метод. Похож на предыдущий, но возвращает значение в зависимости от того, продолжается ли дерево
get(value) - возвращает поддерево со значением корня value
min() - возвращает поддерево с минимальным значением корня
max() - возвращает поддерево с максимальным значением корня
next() - возвращает поддерево - следующий элемент в линейной записи
prev() - возвращает поддерево - предыдущий элемент в линейной записи
insert(value) - добавляет в дерево узел со значением value
delete(value) - удаляет из дерева узел со значением value

tree - tuple поле, хранящее карту дерева
value - int поле, хранящее значение корня дерева
children - list поле, хранящее [] в случае листа и [left, right] в ином случае
left - ссылка на левого ребенка
right - ссылка на правого ребенка
level - int поле, хранящее уровень дерева
parent - ссылка на родителя дерева, если такой имеется, в ином случае None
color - bool поле, хранящее цвет: False - черный, True - красный



#skew()
#split()
#используются для балансировки дерева при добавлении и удалении элементов




справка:
чтобы создать объект дерева, класть в инит правильный словарь, а именно:
1) словарь должен иметь один ключ и каждое значение словаря должно иметь два значения внутри (верно для каждого вложенного словаря)
2) левый лист имеет запись {float("-inf"): {}}
3) правый лист имеет запись {float("+inf"): {}}
"""