Сбалансированные деревья: AVL и Red-Black

Проблема несбалансированности

BST на отсортированных данных вырождается в список. Вставка [1, 2, 3, 4, 5] даёт:

1
 \
  2
   \
    3  ← высота O(n), поиск O(n)

Сбалансированные деревья поддерживают h = O(log n) автоматически.

AVL-дерево

Для каждого узла баланс-фактор = height(right) - height(left) ∈ {-1, 0, 1}. При нарушении выполняются повороты.

Четыре случая разбалансировки:

func rotateRight[T any](y *TreeNode[T]) *TreeNode[T] {
    x := y.Left
    y.Left = x.Right
    x.Right = y
    // обновить высоты y, затем x
    return x
}

AVL гарантирует h ≤ 1.44 log₂(n+2). Поиск быстрее Red-Black, вставка/удаление медленнее.

Red-Black дерево

Каждый узел окрашен в красный или чёрный. Инварианты:

1. Корень — чёрный.
2. Красный узел имеет только чёрных детей.
3. Все пути от корня до листьев содержат одинаковое число чёрных узлов.

Высота ≤ 2 log₂(n+1). Меньше поворотов при вставке/удалении, чем AVL.

Go использует Red-Black деревья в пакете golang.org/x/exp/maps и в рантайме планировщика горутин.

Практика в Go

В большинстве случаев не нужна ручная реализация:

// Для упорядоченных данных — btree из расширенной библиотеки
import "golang.org/x/exp/maps"

// Для простых случаев — отсортированный срез + бинарный поиск
data := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(data, 5)

// Сторонний пакет с готовым AVL/RB:
// github.com/emirpasic/gods

Упражнения