Какая скорость в бинарном дереве?

Временная сложность операций в бинарном дереве

Бинарное дерево — это одна из самых фундаментальных структур данных. Скорость операций зависит от типа дерева и его сбалансированности. Давайте разберём основные варианты.

Обычное несбалансированное бинарное дерево

Для обычного бинарного дерева поиска (BST) без гарантий баланса:

• Поиск (Search): O(h), где h — высота дерева
• Вставка (Insert): O(h)
• Удаление (Delete): O(h)
• Обход (Traversal): O(n)

Высота h может быть от log(n) до n — всё зависит от того, как вставляются данные:

# Худший случай — дерево как связный список
root = Node(1)
root.right = Node(2)
root.right.right = Node(3)
root.right.right.right = Node(4)  # высота = 4, это O(n)

# Лучший случай — идеально сбалансированное дерево
#      2
#     / \\
#    1   3
# высота = 2, это O(log n)

Сбалансированное бинарное дерево (AVL, Red-Black)

Для сбалансированных деревьев (AVL, Red-Black Tree) дерево автоматически перестраивается:

• Поиск: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)
• Обход: O(n)

Это гарантируется тем, что разница высот левого и правого поддеревьев остаётся ≤ 1.

Полное бинарное дерево

Для полного бинарного дерева (каждый уровень полностью заполнен):

• Высота: O(log n)
• Поиск: O(log n) в best/average случае
• Вставка: O(n) если нужно перестраивать, но обычно O(log n)

Практическая сравнительная таблица

Операция        | Несбалансированное | Сбалансированное
----------------|-------------------|------------------
Поиск           | O(log n) - O(n)   | O(log n)
Вставка         | O(log n) - O(n)   | O(log n)
Удаление        | O(log n) - O(n)   | O(log n)
Обход           | O(n)              | O(n)

Примеры на Python

Простое бинарное дерево поиска:

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):  # O(h)
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)
    
    def _insert_recursive(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
            else:
                self._insert_recursive(node.left, val)
        else:
            if node.right is None:
                node.right = TreeNode(val)
            else:
                self._insert_recursive(node.right, val)
    
    def search(self, val):  # O(h)
        return self._search_recursive(self.root, val)
    
    def _search_recursive(self, node, val):
        if node is None:
            return False
        if node.val == val:
            return True
        elif val < node.val:
            return self._search_recursive(node.left, val)
        else:
            return self._search_recursive(node.right, val)

Сбалансированное дерево (AVL-подобное):

from collections import deque

class AVLNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def insert(self, node, val):  # O(log n)
        if not node:
            return AVLNode(val)
        
        if val < node.val:
            node.left = self.insert(node.left, val)
        else:
            node.right = self.insert(node.right, val)
        
        # Обновляем высоту и балансируем
        node.height = 1 + max(self._height(node.left), self._height(node.right))
        
        # Проверяем баланс
        balance = self._get_balance(node)
        
        # Левый случай
        if balance > 1 and val < node.left.val:
            return self._rotate_right(node)
        
        # Правый случай
        if balance < -1 and val > node.right.val:
            return self._rotate_left(node)
        
        return node
    
    def _height(self, node):
        return node.height if node else 0
    
    def _get_balance(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0
    
    def _rotate_left(self, z):
        y = z.right
        z.right = y.left
        y.left = z
        z.height = 1 + max(self._height(z.left), self._height(z.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        return y
    
    def _rotate_right(self, z):
        y = z.left
        z.left = y.right
        y.right = z
        z.height = 1 + max(self._height(z.left), self._height(z.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        return y

Пространственная сложность

• Несбалансированное дерево: O(n) в худшем случае (очень глубокое)
• Сбалансированное дерево: O(n) (хранит n узлов), но с лучшей структурой
• Рекурсивные операции: O(h) доп. памяти на стеке вызовов

Когда использовать

Обычное BST:

• Если данные приходят близко к отсортированному виду
• Для простых прототипов

Сбалансированное дерево (AVL, Red-Black):

• Когда нужны гарантированные O(log n) операции
• В production коде
• Когда непредсказуем порядок вставок

В Python: используй встроенные структуры (dict, set) или библиотеку sortedcontainers — они уже оптимизированы.