Что такое двоичное дерево поиска и зачем его балансировать?

Свойство дерева поиска: все ключи левого поддерева меньше ключа узла, все ключи правого — больше. Поиск, вставка и удаление начинаются с корня и на каждом шаге идут влево или вправо, поэтому стоят O(h), где h — высота дерева.

Проблема вырождения. Если вставлять ключи по возрастанию, каждый новый ключ уходит вправо, и дерево превращается в цепочку высотой n — операции становятся O(n).

Сбалансированные деревья поддерживают высоту O(log n):

• AVL — высоты поддеревьев любого узла отличаются не больше чем на 1; после вставки нарушение исправляют поворотами. Строже сбалансировано — быстрее поиск;
• красно-чёрное — более мягкое правило через раскраску узлов, меньше поворотов при вставке. Используется в TreeMap в Java и std::map в C++.

Обходы дерева:

• in-order (лево, узел, право) — ключи по возрастанию;
• pre-order (узел, лево, право) — копирование и сериализация дерева;
• post-order (лево, право, узел) — удаление, подсчёт размеров поддеревьев;
• по уровням — обход в ширину через очередь.

Сравнение с хеш-таблицей: хеш быстрее в среднем (O(1)), а дерево хранит ключи упорядоченными — даёт минимум, максимум, диапазоны и ближайший ключ.

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []