Каков был бы самый питонный способ реализации общей длины для листовых узлов в дереве?
В следующем примере я использую переменную класса, которая прекрасно работает, когда есть только одно дерево, но не когда их два или более (потому что переменная класса влияет на каждый Node экземпляр, а не только на экземпляры вконкретное дерево).
class _Node:
"""
"""
_global_end = 0
def __init__(self, start: int, size: int = 0):
self.start: int = int(start)
self._size: int = int(size)
self.children: dict = {}
def __repr__(self):
return "Node({0.start}:{0.end})".format(self)
@classmethod
def _get_end(cls) -> int:
return cls._global_end
@classmethod
def global_extend(cls, increment: int = 1):
cls._global_end += increment
@property
def is_leaf(self) -> bool:
return not self.children
@property
def end(self) -> int:
if self.is_leaf:
return self._get_end()
return self.start + self._size
@property
def size(self) -> int:
return self.end - self.start
@size.setter
def size(self, value: int):
if self.is_leaf:
raise AttributeError('cannot resize leaves individually')
self._size = value
def add_child(self, name: str, start: int, size: int = 0) -> None:
self.children[name] = _Node(start, size)
def set_child(self, name: str, child: '_Node') -> None:
self.children[name] = child
Очевидно, что можно было бы создать что-то вроде объекта class End и передать его функции-конструктору Node, но это выглядит грязно, потому что структура данных Tree тогда должна будетзнать как о Node зависимости, так и о зависимости самого класса Node.
Смысл этого в том, чтобы в классе Tree был метод, который может изменять размер всех конечных узлов за O (1) времени путем изменения одной переменной.
Очевидно, что для того, чтобы дерево оставалось действительным, внутренние узлы не должны изменяться, когда листья изменяются.Кроме того, для того, чтобы существовало несколько действительных деревьев (каждое из которых составлено из групп связанных узлов), должна быть возможность работать с каждым из них по отдельности, не влияя на другие.