from collections import deque
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
@property
def is_leaf(self):
return self.left is None and self.right is None
class MinMaxPath:
def __init__(self):
self.min = float("inf")
self.max = float("-inf")
self.current = []
self.result_min = None
self.result_max = None
self.sum = 0
class Tree:
def __init__(self):
self.root = None
self.size = 0
def insert(self, key):
self.root = self._insert(self.root, key)
self.size += 1
def _insert(self, node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = self._insert(node.left, key)
else:
node.right = self._insert(node.right, key)
return node
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None:
return False
if node.key == key:
return True
if key < node.key:
return self._search(node.left, key)
return self._search(node.right, key)
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if node.left is None and node.right is None:
self.size -= 1
return None
elif node.left is None or node.right is None:
self.size -= 1
return node.left or node.right
m = self._find_min(node.right)
node.key = m.key
node.right = self._delete(node.right, m.key)
return node
@staticmethod
def _find_min(node):
while node.left:
node = node.left
return node
def find_path(self, a, b):
"""
для нахождения путей от корня до листа длины в диапазоне [a, b], за один обход дерева
"""
result = []
current_path = []
self._find_path(self.root, current_path, result, a, b)
return result
def _find_path(self, node, current_path, result, a, b):
if node is None:
return
current_path.append(node.key)
if node.is_leaf:
if a <= (len(current_path)-1) <= b:
result.append(current_path.copy())
self._find_path(node.left, current_path, result, a, b)
self._find_path(node.right, current_path, result, a, b)
current_path.pop()
def find_path_n(self, n):
"""
для нахождения путей от корня до листа, имеющих сумму значений в узлах, равную N, за один обход дерева
"""
result = []
current_path = []
s = 0
self._find_path_n(self.root, current_path, s, n, result)
return result
def _find_path_n(self, node, current_path, s, n, result):
if node is None:
return
s += node.key
current_path.append(node.key)
if node.is_leaf:
if s == n:
result.append(current_path.copy())
self._find_path_n(node.left, current_path, s, n, result)
self._find_path_n(node.right, current_path, s, n, result)
current_path.pop()
def find_path_m(self):
"""
для нахождения путей от корня до листа, имеющих максимальную и минимальную сумму значений в узлах, за один обход дерева.
"""
path = MinMaxPath()
self._find_path_m(self.root, path)
return path.result_max, path.result_min
def _find_path_m(self, node, path: MinMaxPath):
if node is None:
return
path.current.append(node.key)
path.sum += node.key
if node.is_leaf:
if path.sum > path.max:
path.max = path.sum
path.result_max = path.current.copy()
if path.sum < path.min:
path.min = path.sum
path.result_min = path.current.copy()
self._find_path_m(node.left, path)
self._find_path_m(node.right, path)
path.current.pop()
path.sum -= node.key
def is_sym(self):
"""
для проверки, является ли бинарное дерево симметричным по значениям в узлах относительно своего центра (корня)
обход вглубь (рекурсивный)
"""
if self.root is None: return True
return self._is_sym(self.root.left, self.root.right)
def _is_sym(self, left, right):
if left is None and right is None: return True
if left is None or right is None: return False
if left.key != right.key: return False
return self._is_sym(left.left, right.right) and self._is_sym(left.right, right.left)
def issym(self):
"""
для проверки, является ли бинарное дерево симметричным по значениям в узлах относительно своего центра (корня)
обход в ширину (итеративный)
"""
if self.root is None: return True
queue = deque([(self.root.left, self.root.right)])
while queue:
left, right = queue.popleft()
if left is None and right is None: return True
if left is None or right is None: return False
if left.key != right.key: return False
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True
def is_max_heap_n(self, n):
"""
кучей (мин или макс) с количеством элементов больше N;
"""
queue = deque([self.root])
gap = False
size = 0
while queue:
node = queue.popleft()
if node is None:
gap = True
continue
elif gap:
return False
if node.left and node.left.key > node.key:
return False
if node.right and node.right.key > node.key:
return False
size += 1
queue.append(node.left)
queue.append(node.right)
return size > n
def is_max_heap_ab(self, a, b):
"""
кучей (мин или макс) высотой больше А и меньше В;
"""
queue = deque([self.root])
gap = False
height = -1
while queue:
level_size = len(queue)
height += 1
for _ in range(level_size):
node = queue.popleft()
if node is None:
gap = True
continue
elif gap:
return False
if node.left and node.left.key > node.key:
return False
if node.right and node.right.key > node.key:
return False
queue.append(node.left)
queue.append(node.right)
return a < height < b
def is_lin(self, c, d):
"""
линейным списком с диапазоном значений [c, d];
"""
def _is_lin(node):
if node is None:
return True
if node.left and node.right:
return False
if not c <= node.key <= d:
return False
return _is_lin(node.left or node.right)
return _is_lin(self.root)
def is_search(self, n):
"""
деревом поиска с высотой больше N.
"""
def _is_search(node, minv, maxv):
if node is None:
return True, -1
if not minv < node.key < maxv:
return False, -1
left, height_l = _is_search(node.left, minv, node.key)
right, height_r = _is_search(node.right, node.key, maxv)
is_search = left and right
height = 1 + max(height_l, height_r)
return is_search, height
s, h = _is_search(self.root, float("-inf"), float("inf"))
return s and h > n
def is_search_cd(self, c, d):
"""
деревом поиска с элементами из диапазона [c, d];
"""
def _is_search_cd(node, minv, maxv):
if node is None:
return True
if (not c <= node.key <= d) or (not minv <= node.key <= maxv):
return False
return _is_search_cd(node.left, minv, node.key) and _is_search_cd(node.right, node.key, maxv)
return _is_search_cd(self.root, float("-inf"), float("inf"))
def is_avl(self, a, b):
"""
АВЛ-деревом высотой больше А и меньше В
"""
def _is_avl(node, minv, maxv):
if node is None:
return True, -1
if not minv < node.key < maxv:
return False, -1
left, lh = _is_avl(node.left, minv, node.key)
right, rh = _is_avl(node.right, node.key, maxv)
avl = right and left
if abs(lh-rh) > 1:
avl = False
height = 1 + max(lh, rh)
return avl, height
r, h = _is_avl(self.root, float("-inf"), float("inf"))
return r and a < h < b
def bfs(self):
"""
Реализуйте обход бинарного дерева в ширину для подсчёта его высоты и количества узлов на каждом уровне
"""
if self.root is None:
return
queue = deque([self.root])
level = 0
while queue:
level += 1
level_size = len(queue)
print(f"{level}: {level_size}")
for _ in range(level_size):
node = queue.popleft()
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
def nlr(self):
"""
Реализуйте обход бинарного дерева в глубину: прямой
"""
def _nlr(node: Node):
if node is None: return []
return [node.key] + _nlr(node.left) + _nlr(node.right)
return _nlr(self.root)
def lnr(self):
"""
Реализуйте обход бинарного дерева в глубину: центрированный
"""
def _lnr(node: Node):
if node is None: return []
return _lnr(node.left) + [node.key] + _lnr(node.right)
return _lnr(self.root)
def lrn(self):
"""
Реализуйте обход бинарного дерева в глубину: обратный
"""
def _lrn(node: Node):
if node is None: return []
return _lrn(node.left) + _lrn(node.right) + [node.key]
return _lrn(self.root)