Исходный код EJIO.utils.component.tree.bst

## /utils/component/tree/bst.py

from collections.abc import Iterator, Iterable
from threading import RLock
from typing import Any
from ...struct import TreeNode, Stack

__all__ = [
    'BSTNode',
]




class BSTNode(TreeNode):
    """
    Узел двоичного (бинарного) дерева поиска (Binary Search Tree).
    Содержит строго левого (меньшего) и правого (большего) потомков.
    """
    __slots__ = ('_value', 'left', 'right', '_lock')

    def __init__(self, *args: Any) -> None:
        """
        Инициализирует узел бинарного дерева поиска.

        Примеры:
        BSTNode(50)                    # Одиночный корень
        BSTNode([50, 30, 70, 20, 40])  # Автоматическое построение дерева из списка/итератора
        """
        self._value: Any = None
        self.left: 'BSTNode | None' = None
        self.right: 'BSTNode | None' = None
        self._lock: RLock = RLock()

        if args:
            if len(args) == 1 and isinstance(args[0], Iterable) and not isinstance(args[0], str):
                iterator: Iterator[Any] = iter(args[0])
                try:
                    self._value = next(iterator)
                    for item in iterator:
                        self.insert(item)
                except StopIteration:
                    pass
            else:
                if len(args) == 1:
                    self._value = args[0]
                else:
                    self._value = args[0]
                    for item in args[1:]:
                        self.insert(item)

    @property
    def value(self) -> Any:
        """
        Возвращает значение текущего узла.

        :return: Значение текущего узла.
        """
        with self._lock:
            return self._value

    @property
    def children(self) -> Iterable[TreeNode]:
        """
        Потокобезопасная проекция двоичной структуры на общий контракт TreeNode.
        Возвращает левого и правого детей, если они существуют.

        :return: Список потомков.
        """
        with self._lock:
            res = []
            if self.left is not None:
                res.append(self.left)
            if self.right is not None:
                res.append(self.right)
            return res



    def insert(self, val: Any) -> None:
        """
        Потокобезопасная упорядоченная вставка элемента со сравнением значений.

        :param val: Значение нового узла.
        """
        with self._lock:
            if val < self._value:
                if self.left is None:
                    self.left = BSTNode(val)
                else:
                    self.left.insert(val)
            else:
                if self.right is None:
                    self.right = BSTNode(val)
                else:
                    self.right.insert(val)




    def destroy(self) -> None:
        """
        Итеративное, потокобезопасное и каскадное уничтожение бинарного дерева поиска.
        Полностью защищено от RecursionError и оптимизировано по скорости.
        """
        with self._lock:
            if self._value is None:
                return  # Дерево уже уничтожено

            # Создаем итеративный стек для обхода всех узлов
            nodes_stack: Stack[BSTNode] = Stack()
            nodes_stack.push(self)

            # Массив для плоского сбора всех узлов, подлежащих очистке
            nodes_to_clear: list[BSTNode] = []

            # Шаг 1: Итеративно собираем все узлы в плоский список (без рекурсии)
            while not nodes_stack.empty:
                current_node = nodes_stack.pop()
                if current_node is None:
                    continue

                nodes_to_clear.append(current_node)

                # Заталкиваем детей в стек
                if current_node.left is not None:
                    nodes_stack.push(current_node.left)
                if current_node.right is not None:
                    nodes_stack.push(current_node.right)

            # Шаг 2: Обходим собранные узлы с конца и жестко зануляем их внутренности
            # Это гарантирует, что мы сначала отвяжем листья, а затем родительские ветви
            for node in reversed(nodes_to_clear):
                # Захватываем локальный замок каждого конкретного узла перед очисткой
                with node._lock:
                    node.left = None
                    node.right = None
                    node._value = None
                # Высвобождаем ссылку на сам замок узла
                node._lock = None  # type: ignore[assignment]

        # Зануляем локальный замок корневого узла
        self._lock = None  # type: ignore[assignment]


    def __repr__(self) -> str:
        """
        Строковое представление узла.

        :return: Представление узла в виде строки.
        """
        with self._lock:
            return f"BSTNode({self._value!r})"