lynulx

Untitled

Oct 27th, 2021
786
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from typing import List
  2.  
  3.  
  4. class BinSearchTree(dict):
  5.     def __init__(self, tree_dict: dict):
  6.         self.tree: dict = tree_dict
  7.         self.parent = None
  8.         if tree_dict in ({float("+inf"): {}}, {float("-inf"): {}}):
  9.             self._leaf_init()
  10.         else:
  11.             left, right = list(tree_dict.values())[0].items()
  12.             if self.is_leaf(left) and self.is_leaf(right):
  13.                 self._empty_node_init()
  14.             else:
  15.                 self._subtree_init()
  16.    
  17.     def __repr__(self):
  18.         return self.tree.__repr__()
  19.  
  20.     def is_leaf(self, tree_dict=None):
  21.         if tree_dict is None:
  22.             tree_dict = self.tree
  23.         if tree_dict in ({float("+inf"): {}}, {float("-inf"): {}}) or \
  24.             (
  25.             isinstance(tree_dict, type(self)) and\
  26.             tree_dict.value == [] and\
  27.             tree_dict.children == [] and\
  28.             tree_dict.level == 1):
  29.             return True
  30.         return False
  31.  
  32.     def is_empty_node(self, tree_dict=None):
  33.         if self.is_leaf(): return False
  34.         if tree_dict is None:
  35.             tree_dict = self.tree
  36.         value = list(tree_dict.keys())[0]  # только 1 элемент
  37.         left, right = tree_dict[value].items()
  38.         left = {left[0]: left[1]}
  39.         right = {right[0]: right[1]}
  40.         return value is not None and \
  41.             (
  42.                 all([
  43.                 left == {float("-inf"): {}},
  44.                 right == {float("+inf"): {}}])
  45.                 or \
  46.                 (
  47.                     isinstance(tree_dict, type(self)) and\
  48.                     tree_dict.value == list(tree_dict.keys()) and\
  49.                     tree_dict.children == [AATree({}), AATree({})] and\
  50.                     tree_dict.level == 1
  51.  
  52.                 )
  53.             )
  54.  
  55.     def _leaf_init(self):
  56.         self.value: list = []
  57.         self.children: list = []
  58.         self.level: int = 1
  59.         if self.parent is not None and self is self.parent.right:
  60.             self.tree = {float("+inf"): {}}
  61.         else:
  62.             self.tree = {float("-inf"): {}}
  63.  
  64.     def _empty_node_init(self):
  65.         tree_dict = self.tree
  66.         self.value: list = list(tree_dict.keys())
  67.         self.children: list = [AATree({}), AATree({})]
  68.         self.left, self.right = self.children
  69.         self.level: int = 1
  70.         self.left.parent = self
  71.         self.right.parent = self
  72.         self.tree = {self.value: {
  73.             None: {},
  74.             None: {}
  75.         }}
  76.        
  77.     def _subtree_init(self):
  78.         tree_dict = self.tree
  79.         Node = type(self)
  80.         self.value: list = list(tree_dict.keys())  # 1 element
  81.         left, right = tree_dict[self.value[0]].items()
  82.         left = {left[0]: left[1]}
  83.         right = {right[0]: right[1]}
  84.         self.children: List[Node] = [Node(left), Node(right)]
  85.         self.left, self.right = self.children
  86.         self.level: int = min([self.left.level, self.right.level]) + 1
  87.         self.left.parent = self
  88.         self.right.parent = self
  89.         self.left.tree = left
  90.         self.right.tree = right
  91.    
  92.     def get(self, value):
  93.         if self.value == [value]:
  94.             return self
  95.         elif self.is_leaf() or self.is_empty_node():
  96.             raise ValueError("tree has no such value in it")
  97.         elif value < self.value[0]:
  98.             return self.left.get(value)
  99.         elif value > self.value[0]:
  100.             return self.right.get(value)
  101.  
  102.     def min(self):
  103.         if self.is_leaf(): return float("+inf")
  104.         elif self.left.is_leaf():
  105.             return self
  106.         else:
  107.             return self.left.min()
  108.    
  109.     def max(self):
  110.         if self.is_leaf(): return float("-inf")
  111.         elif self.right.is_leaf():
  112.             return self
  113.         else:
  114.             return self.right.max()
  115.    
  116.     def next(self):
  117.         try:
  118.             if not self.right.is_leaf():
  119.                 return self.right.min()
  120.             parent = self.parent
  121.             while not parent.is_leaf() and self == parent.right:
  122.                 self = parent
  123.                 parent = parent.parent
  124.             return parent
  125.         finally:
  126.             self._fix_level()
  127.    
  128.     def prev(self):
  129.         try:
  130.             if not self.left.is_leaf:
  131.                 return self.left.max()
  132.             parent = self.parent
  133.             while not parent is None and self == parent.left:
  134.                 self = parent
  135.                 parent = parent.parent
  136.             return parent
  137.         finally:
  138.             self._fix_level()
  139.    
  140.     def insert(self, value: int):
  141.         Node = type(self)
  142.         if self.is_leaf(self):
  143.             self = Node({value: {None: {}, None: {}}})
  144.         elif value < self.value:
  145.             self.left.insert(value)
  146.         elif value > self.value:
  147.             self.right.insert(value)
  148.         self._fix_level()
  149.    
  150.     def delete(self, value):
  151.         Node = type(self)
  152.         if self.is_leaf(self):
  153.             pass
  154.         if value < self.value:
  155.             self.left.delete(value)
  156.         elif value > self.value:
  157.             value.right.delete(value)
  158.         elif not (value.left.is_leaf() or self.right.is_leaf()):
  159.             self.value = self.min().value
  160.             self.tree = {self.value: list(self.tree.values())[0]}
  161.             self.right.delete(self.value)
  162.         else:
  163.             if not self.left.is_leaf():
  164.                 self = self.left
  165.             elif not self.right.is_leaf():
  166.                 self = self.right
  167.             else:
  168.                 self = Node({})
  169.         self._fix_level()
  170.  
  171.     def _root_lvl_from_leaf(self):
  172.         if self.is_leaf:
  173.             self.level = 1
  174.         if not self.parent is None:
  175.             parent = self.parent
  176.             left = parent.left
  177.             parent.level = left.level + 1
  178.             parent._fix_level(self)
  179.         if self.parent is None:
  180.             return self.level
  181.  
  182.     def _min_lvl_from_root_unfixed(self, root_lvl) -> int:
  183.         if self.is_leaf():
  184.             return 1
  185.         left, right = self.children
  186.         left.level = root_lvl - 1
  187.         right.level = root_lvl - 1
  188.         if right.is_leaf():
  189.             min_left_lvl = left._min_lvl_from_root_unfixed(left.level)
  190.             return min(min_left_lvl, root_lvl - 1)
  191.         elif left.is_leaf():
  192.             min_right_lvl = right._min_lvl_from_root_unfixed(right.level)
  193.             return min(min_right_lvl, root_lvl - 1)
  194.         else:
  195.             return left._min_lvl_from_root_unfixed(left.level)
  196.        
  197.  
  198.  
  199.     def _add_level(self, lvl2add: int):
  200.         self.level += lvl2add
  201.         if not self.is_leaf():
  202.             self.left._add_level(lvl2add)
  203.             self.right._add_level(lvl2add)
  204.  
  205.     def _fix_level(self):
  206.         root_lvl = self._root_lvl_from_leaf()
  207.         min_leaf_lvl = self._min_lvl_from_root_unfixed(root_lvl)
  208.         self._add_level(1 - min_leaf_lvl)
  209.  
  210.  
  211.  
  212. class RBTree(BinSearchTree):
  213.     def __init__(self, tree_dict: dict):
  214.         super().__init__(tree_dict)
  215.         if self.is_leaf():
  216.             self.color: bool = False  # False for black, True for red
  217.         else:
  218.             self.color: bool = not min(self.children, key=lambda x: x.value).color
  219.  
  220.     def next(self):
  221.         try:
  222.             return super().next()
  223.         finally:
  224.             self.__fix_colors()
  225.    
  226.     def prev(self):
  227.         try:
  228.             super().prev()
  229.         finally:
  230.             self.__fix_colors()
  231.    
  232.     def insert(self, value: int):
  233.         super().insert(value)
  234.         self.__fix_colors()
  235.    
  236.     def delete(self, value):
  237.         super().delete(value)
  238.         self.__fix_colors()
  239.  
  240.     def __fix_colors(self):
  241.         self._fix_level()
  242.         if self.is_leaf(self):
  243.             self.color = False  # black
  244.         else:
  245.             self.color = bool((self.level + 1) % 2)
  246.  
  247.  
  248.  
  249. class AATree(RBTree):
  250.     def __init__(self, tree_dict: dict):
  251.         super().__init__(tree_dict)
  252.  
  253.     def skew(self):
  254.         # не делаю классметодом потому что
  255.         # метод должен делать взаимодействовать с объектом
  256.         Node = type(self)
  257.         if not self.is_leaf and not self.left.is_leaf():
  258.             self = Node(
  259.                 {
  260.                     self.left.value: {
  261.                         **self.left.left,
  262.                         self.value: {
  263.                             **self.left.right,
  264.                             **self.right
  265.                         }
  266.                     }
  267.                 }
  268.             )
  269.         self.__fix_colors()
  270.    
  271.     def split(self):  # tree: AAtree
  272.         if self.is_leaf() or \
  273.            self.right.is_leaf() or \
  274.            self.right.right.is_leaf():
  275.             pass
  276.         elif not any([
  277.             self.is_leaf(),
  278.             self.right.is_leaf(),
  279.             self.right.right.is_leaf()
  280.             ]) and self.level == self.right.right.level:
  281.             self = {
  282.                 self.right.value: {
  283.                     self.value: {
  284.                         **self.left,
  285.                         **self.right.left
  286.                     },
  287.                     **self.right.right
  288.                 }
  289.             }
  290.         self.__fix_colors()
  291.    
  292.     def insert(self, value: int):
  293.         Node = type(self)
  294.         if self.is_leaf(self):
  295.             self = Node({value: {}})
  296.         elif value < self.value[0]:
  297.             self.left.insert(value)
  298.         elif value > self.value[0]:
  299.             self.right.insert(value)
  300.         self.skew()
  301.         self.split()
  302.         self.__fix_colors()
  303.    
  304.     def __decrease_level(self):
  305.         if self.children == []:
  306.             right_level = 1
  307.         else:
  308.             right_level = min(self.children, key = lambda x: x.level).level + 1
  309.         if right_level < self.level:
  310.             self.level = right_level
  311.             if right_level < self.right.level:
  312.                 self.right.level = right_level
  313.         self.__fix_colors()
  314.    
  315.     def delete(self, value: int):
  316.         if not self.is_leaf(self):
  317.             if value > self.value[0]:
  318.                 self.right.delete(value)
  319.             elif value < self.value[0]:
  320.                 self.right.delete(value)
  321.             elif self.left.is_leaf():
  322.                 successor = self.successor()
  323.                 right = self.right
  324.                 right.delete(successor.value)
  325.                 self.value = successor.value
  326.             else:
  327.                 predecessor = self.predecessor()
  328.                 left = self.left
  329.                 left.delete(predecessor.value)
  330.                 self.value = predecessor.value
  331.         self.__decrease_level()
  332.         self.skew()
  333.         if not self.is_leaf():
  334.             self.right.skew()
  335.             if not self.right.is_leaf():
  336.                 self.right.right.skew()
  337.         self.split()
  338.         if not self.is_leaf():  self.right.split()
  339.         self.__fix_colors()
  340.  
  341.     def __fix_colors(self):
  342.         if self.is_leaf(self):
  343.             self.color = False  # black
  344.         else:
  345.             self.color = bool((self.level + 1) % 2)
  346.            
  347.  
  348.  
  349. if __name__ == "__main__":
  350.     from pprint import pprint
  351.     dict_example = {
  352.         13: {
  353.             8: {
  354.                 1: {
  355.                     float("-inf"): {},
  356.                     6: {
  357.                         float("-inf"): {},
  358.                         float("+inf"): {}
  359.                         }
  360.                     },
  361.                 11: {
  362.                     float("-inf"): {},
  363.                     float("+inf"): {}
  364.                     }
  365.                 },
  366.             17: {
  367.                 15: {
  368.                     float("-inf"): {},
  369.                     float("+inf"): {}
  370.                     },
  371.                 25: {
  372.                     22: {
  373.                         float("-inf"): {},
  374.                         float("+inf"): {}
  375.                         },
  376.                     27: {
  377.                         float("-inf"): {},
  378.                         float("+inf"): {}
  379.                         }
  380.                     }
  381.                 }
  382.             }
  383.         }
  384.     tree = AATree(dict_example)
  385.     pprint(tree.get(25))
  386.     print(tree.value)
  387.  
  388.  
  389.  
  390. """
  391. AATree - класс
  392.  
  393. вывод (__repr__()) - позволяет выводить объект в консоль, например, принтом, выводит карту дерева
  394. is_leaf() - bool метод, возвращает значение в зависимости от того, лист ли дерево (лист - True)
  395. is_empty_node() - bool метод. Похож на предыдущий, но возвращает значение в зависимости от того, продолжается ли дерево
  396. get(value) - возвращает поддерево со значением корня value
  397. min() - возвращает поддерево с минимальным значением корня
  398. max() - возвращает поддерево с максимальным значением корня
  399. next() - возвращает поддерево - следующий элемент в линейной записи
  400. prev() - возвращает поддерево - предыдущий элемент в линейной записи
  401. insert(value) - добавляет в дерево узел со значением value
  402. delete(value) - удаляет из дерева узел со значением value
  403.  
  404. tree - tuple поле, хранящее карту дерева
  405. value - int поле, хранящее значение корня дерева
  406. children - list поле, хранящее [] в случае листа и [left, right] в ином случае
  407. left - ссылка на левого ребенка
  408. right - ссылка на правого ребенка
  409. level - int поле, хранящее уровень дерева
  410. parent - ссылка на родителя дерева, если такой имеется, в ином случае None
  411. color - bool поле, хранящее цвет: False - черный, True - красный
  412.  
  413.  
  414.  
  415. #skew()
  416. #split()
  417. #используются для балансировки дерева при добавлении и удалении элементов
  418.  
  419.  
  420.  
  421.  
  422. справка:
  423. чтобы создать объект дерева, класть в инит правильный словарь, а именно:
  424. 1) словарь должен иметь один ключ и каждое значение словаря должно иметь два значения внутри (верно для каждого вложенного словаря)
  425. 2) левый лист имеет запись {float("-inf"): {}}
  426. 3) правый лист имеет запись {float("+inf"): {}}
  427. """
  428.  
RAW Paste Data