> Что такое сбалансированное дерево (Go)

Короткий ответ

Сбалансированное дерево - это структура данных, в которой высота левого и правого поддеревьев для каждого узла отличается не более чем на единицу (для AVL-деревьев) или соблюдается более мягкое условие (например, для красно-чёрных деревьев). Балансировка гарантирует, что операции поиска, вставки и удаления выполняются за O(log n), а не вырождаются в O(n), как в худшем случае для обычного бинарного дерева поиска.

Подробное объяснение

В несбалансированном бинарном дереве поиска при последовательной вставке отсортированных данных дерево вырождается в связный список - высота становится равной количеству элементов n, и все операции становятся линейными. Сбалансированные деревья решают эту проблему, автоматически перестраивая структуру при вставке и удалении.

Основные виды сбалансированных деревьев:

• AVL-дерево - строгая балансировка: для каждого узла разница высот поддеревьев не более 1. Использует повороты (left, right, left-right, right-left) для восстановления баланса.
• Красно-чёрное дерево - менее строгая балансировка: каждый узел окрашен в красный или чёрный цвет, соблюдаются пять инвариантов. Гарантирует высоту не более 2·log(n+1). Используется в стандартных библиотеках (например, в Go - map на основе хеш-таблицы, но в C++ std::map - красно-чёрное дерево).
• B-дерево и его варианты - сбалансированное дерево с множеством ключей в узле, используется в базах данных и файловых системах.

Ключевое свойство: высота сбалансированного дерева всегда O(log n), что обеспечивает логарифмическую сложность основных операций.

На практике

В Go стандартная библиотека не предоставляет готовых сбалансированных деревьев - для упорядоченных данных обычно используют sort.Search со срезом или внешние библиотеки (например, github.com/google/btree). Однако понимание принципов балансировки важно для:

• реализации собственных структур данных;
• анализа сложности алгоритмов;
• понимания внутреннего устройства баз данных (B-деревья);
• решения задач на собеседованиях, где требуется реализовать дерево.

На практике в backend-разработке чаще встречаются B-деревья (в PostgreSQL, MongoDB) и LSM-деревья (в LevelDB, RocksDB), но базовые принципы балансировки одинаковы.

Пример кода

Простая реализация AVL-дерева на Go:

GO
type Node struct {
    key    int
    height int
    left   *Node
    right  *Node
}

func height(n *Node) int {
    if n == nil {
        return 0
    }
    return n.height
}

func updateHeight(n *Node) {
    lh, rh := height(n.left), height(n.right)
    if lh > rh {
        n.height = lh + 1
    } else {
        n.height = rh + 1
    }
}

func balanceFactor(n *Node) int {
    if n == nil {
        return 0
    }
    return height(n.left) - height(n.right)
}

func rotateRight(y *Node) *Node {
    x := y.left
    t2 := x.right
    x.right = y
    y.left = t2
    updateHeight(y)
    updateHeight(x)
    return x
}

func rotateLeft(x *Node) *Node {
    y := x.right
    t2 := y.left
    y.left = x
    x.right = t2
    updateHeight(x)
    updateHeight(y)
    return y
}

func insert(n *Node, key int) *Node {
    if n == nil {
        return &Node{key: key, height: 1}
    }
    if key < n.key {
        n.left = insert(n.left, key)
    } else if key > n.key {
        n.right = insert(n.right, key)
    } else {
        return n // дубликат
    }
    updateHeight(n)
    bf := balanceFactor(n)
    // левый-левый
    if bf > 1 && key < n.left.key {
        return rotateRight(n)
    }
    // правый-правый
    if bf < -1 && key > n.right.key {
        return rotateLeft(n)
    }
    // левый-правый
    if bf > 1 && key > n.left.key {
        n.left = rotateLeft(n.left)
        return rotateRight(n)
    }
    // правый-левый
    if bf < -1 && key < n.right.key {
        n.right = rotateRight(n.right)
        return rotateLeft(n)
    }
    return n
}

Как отвечать на собеседовании

1. Начни с определения: сбалансированное дерево - это дерево, где высота поддеревьев каждого узла отличается не более чем на заданную константу.
2. Объясни, зачем это нужно: гарантия O(log n) для поиска, вставки, удаления.
3. Приведи примеры: AVL, красно-чёрное, B-дерево.
4. Упомяни trade-off: балансировка требует дополнительных операций при вставке/удалении (повороты, перекрашивание), но это окупается гарантированной производительностью.
5. Если спросят про Go - честно скажи, что в стандартной библиотеке нет готовых сбалансированных деревьев, но есть сторонние реализации, и в целом для упорядоченных данных часто используют сортированные срезы.

Что проверяет интервьюер

• Понимание базовых структур данных и их сложности.
• Умение объяснять trade-off между скоростью операций и сложностью реализации.
• Знание конкретных видов сбалансированных деревьев и их применения.
• Способность рассуждать о том, почему несбалансированное дерево может деградировать до O(n).

Типичные ошибки

• Путаница между AVL и красно-чёрным деревом: AVL строже балансирует, но требует больше поворотов при вставке.
• Утверждение, что сбалансированное дерево всегда идеально сбалансировано (как полное бинарное дерево) - это не так, балансировка гарантирует лишь ограничение на разницу высот.
• Забывают упомянуть, что балансировка нужна именно для бинарных деревьев поиска - обычные деревья (например, деревья разбора) не требуют балансировки.
• Неправильная оценка сложности: говорят O(log n) для всех операций, но забывают, что это амортизированная или гарантированная оценка, а не средняя.