> Пример использования деревьев (Python)

Деревья в Python активно применяются для представления иерархических данных и оптимизации поиска. Например, при реализации файловой системы или парсинга HTML/XML. Рассмотрим простой пример бинарного дерева поиска (BST) для хранения чисел с операциями вставки и поиска:

PYTHON
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None or node.value == value:
            return node
        if value < node.value:
            return self._search_recursive(node.left, value)
        return self._search_recursive(node.right, value)

# Пример использования
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
print(bst.search(5))  # <__main__.TreeNode object>
print(bst.search(20)) # None

Этот код демонстрирует базовую структуру дерева: каждый узел содержит значение и ссылки на левого и правого потомка. Вставка и поиск работают за O(log n) в среднем случае. На практике деревья также используются в алгоритмах сжатия (например, Хаффмана), в базах данных (B-деревья) и для реализации кэширования (LRU-кэш на основе дерева).