from collections import deque
from typing import Iterable
class Node:
def __init__(self, key):
self.key = key
self.children = []
@property
def is_leaf(self):
return len(self.children) == 0
@property
def left(self):
if len(self.children) > 0:
return self.children[0]
return None
@property
def right(self):
if len(self.children) > 1:
return self.children[1]
return None
class NTree:
def __init__(self):
self.root = None
self.size = 0
def insert(self, parent_key, key):
...
def search(self, key):
...
def delete(self, key):
...
def is_binary(self, n):
"""
является ли заданное дерево бинарным деревом поиска с высотой меньше N
"""
if self.root is None:
return n > 0
def isbin(node: Node, minv, maxv):
if node is None:
return True, -1
if len(node.children) > 2:
return False, -1
if not minv < node.key < maxv:
return False, -1
left, lh = isbin(node.left, minv, node.key)
right, rh = isbin(node.right, node.key, maxv)
is_bin = left and right
return is_bin, 1 + max(lh, rh)
is_bin, height = isbin(self.root, float("-inf"), float("inf"))
return is_bin and height < n
def is_avl(self):
"""
Реализуйте функцию проверки является ли заданное N-арное дерево АВЛ-деревом
"""
if self.root is None:
return True
def _isavl(node: Node, minv, maxv):
if node is None:
return True, -1
if len(node.children) > 2:
return False, -1
if not minv < node.key < maxv:
return False, -1
left, lh = _isavl(node.left, minv, node.key)
right, rh = _isavl(node.right, node.key, maxv)
if abs(lh-rh) > 1:
return False, -1
return left and right, 1 + max(lh, rh)
avl, _ = _isavl(self.root, float("-inf"), float("inf"))
return avl
def is_max_heap(self):
"""
Напишите функцию, проверяющую, является ли N-арное дерево кучей (подается корень класса Node),
а также функцию для преобразования существующего дерева в валидную кучу за минимальное количество операций.
Обоснуйте и подтвердите сложность алгоритмов (график теор. и практич. времени)
"""
if self.root is None:
return True
def _is_heap(node: Node):
if node is None:
return True
for child in node.children:
if node.key < child.key or not _is_heap(child):
return False
return True
return _is_heap(self.root)
def heapify(self):
"""
функцию для преобразования существующего дерева в валидную кучу за минимальное количество операций
"""
if self.root is None:
return
def _sift_down(node):
if not node.children:
return
max_child = max(node.children, key=lambda c: c.key)
if max_child.key > node.key:
node.key, max_child.key = max_child.key, node.key
_sift_down(max_child)
def _heapify(node: Node):
if node is None:
return
for child in node.children:
_heapify(child)
_sift_down(node)
def lca(self, c: Iterable):
"""
Напишите функцию для нахождения общего предка для М узлов в N-нарном дереве.
Обоснуйте и подтвердите сложность алгоритмов (график теор. и практич. времени)
"""
if not c or self.root is None:
return None
c = set(c)
m = len(c)
def _lca(node: Node):
if node is None:
return 0, None
f = 1 if node.key in c else 0
result = None
for child in node.children:
s, r = _lca(child)
f += s
if r is not None:
return f, r
if f == m:
result = node
return f, result
_, r = _lca(self.root)
return r.key if r else None
if __name__ == "__main__":
t = NTree()
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)
n9 = Node(9)
n2.children.extend([n5, n6])
n3.children.extend([n7])
n4.children.extend([n8, n9])
n1.children.extend([n2, n3, n4])
t.root = n1
print(t.lca([10]))
print(t.lca([8, 9]))