BST и чем его заменять в Go

Перед началом: бинарные деревья и обходы (модуль 11), бинарный поиск (модуль 10). Инструменты: Go 1.27, sort, slices. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Индекс по ключу стал медленнее в сто раз»

Сервис держал поиск по сессиям в дереве поиска: вставка при логине, поиск на каждом запросе. Год всё было быстро. После релиза с пакетной загрузкой данных из DWH вставки пришли в отсортированном порядке — и поиск упал с 5 до 500 мс. Дерево никто не ломал: оно честно выросло в список. Классический BST от возрастающих ключей вырождается в цепочку высотой n, и его «O(log n)» превращается в O(n) на каждой операции.

В модуле разберём BST как есть — поиск, вставку, удаление с границами и счётчиками — и честно ответим на главный вопрос: что использовать в Go вместо дерева, где его нет в стандартной библиотеке.

📖 Теория

12.1 Свойства BST и цена высоты

BST — дерево, где для каждого узла всё в левом поддереве меньше ключа, а всё в правом — больше. Отсюда инвариант, на который опираются все операции: сравнение с ключом узла отсекает целое поддерево.

Цена операции — O(h), где h — высота. Ключевой факт: BST сам по себе не обещает log n. Высоту задаёт порядок вставок:

• случайные ключи → h ≈ log n (в среднем);
• отсортированные или близкие к ним → h = n (список из инцидента);
• reverse-sorted → тоже h = n.

Это не баг реализации, а свойство структуры: BST без балансировки оптимален только на «достаточно случайном» потоке ключей.

12.2 Поиск, вставка, удаление

Поиск и вставка — это один спуск: на каждом шаге решаем, куда идти.

go
type node struct {
	key         int
	left, right *node
}

// search — спуск по одному сравнени на уровень: O(h).
func search(root *node, key int) *node {
	for root != nil {
		switch {
		case key == root.key:
			return root
		case key < root.key:
			root = root.left
		default:
			root = root.right
		}
	}
	return nil
}

Удаление — три случая, и на собеседовании любят все три:

1. Лист — просто отрезаем.
2. Один ребёнок — ребёнок встаёт на место узла.
3. Двое детей — на место узла приходит successor: минимальный ключ правого поддерева. Его поддерево рекурсивно удаляется той же функцией.

go
func remove(root *node, key int) *node {
	if root == nil {
		return nil
	}
	switch {
	case key < root.key:
		root.left = remove(root.left, key)
	case key > root.key:
		root.right = remove(root.right, key)
	case root.left == nil:
		return root.right // лист или только правый ребёнок
	case root.right == nil:
		return root.left // только левый ребёнок
	default:
		next := minNode(root.right) // successor: минимум справа
		root.key = next.key
		root.right = remove(root.right, next.key)
	}
	return root
}

func minNode(n *node) *node {
	for n.left != nil {
		n = n.left
	}
	return n
}

12.3 Границы, k-й элемент и валидация

Inorder-обход BST отдаёт ключи по возрастанию (модуль 11) — от этого свойства растут три полезные операции.

Валидация. Проверять «левый меньше, правый больше» только у самого узла недостаточно: внук может нарушить границу, не нарушив сравнение с родителем. Корректная проверка передаёт диапазон (lo, hi) вниз:

go
func valid(n *node, lo, hi *int) bool {
	if n == nil {
		return true
	}
	if lo != nil && n.key <= *lo {
		return false
	}
	if hi != nil && n.key >= *hi {
		return false
	}
	return valid(n.left, lo, &n.key) && valid(n.right, &n.key, hi)
}

k-й по величине. Если в узлах хранить размер поддерева, спуск за O(h) без обхода: сравниваем k с размером левого поддерева и уходим в нужную сторону.

floor/ceil и successor. floor — «максимум не больше ключа», ceil — «минимум не меньше». Это те же спуски с запоминанием последнего подходящего узла — их не надо пересчитывать обходом.

12.4 Балансировка: что гарантируют AVL и красно-чёрные

Балансирующиеся деревья держат высоту O(log n) при любом порядке вставок. Две классические схемы:

Обе структуры гарантируют O(log n) на поиск, вставку и удаление. И обе — сложный код: вставка с перебалансировкой — это десятки строк на AVL и разметка цветов на красно-чёрном. Поэтому важно понимать: в стандартной библиотеке Go балансирующегося дерева нет вообще. Не «забыли» — а не включили в контракт языка, оставив выбор прикладному коду.

12.5 Чем заменять дерево в Go

Для подавляющего большинства Go-сервисов «дерево» решается либо отсортированным срезом, либо map — и оба варианта идиоматичнее самописного BST. Самописный BST остаётся отличным учебным упражнением и встречается в собеседованиях, но в проде ему нужно назвать причину.

12.6 Компромиссы

Правило выбора: если вставки и удаления — редкость (обновление справочника раз в минуту), отсортированный срез проще и быстрее дерева на порядок по кэш-поведению. Дерево оправдано, когда мутации частые и нужны диапазонные запросы и набор большой — тогда честно берём внешнюю библиотеку, а не пишем AVL в сервисном коде.

💻 Практика

1. Своя BST с полным набором операций. Реализуйте Insert, Search, Remove (все три случая) и Min/Max. Тесты: пустое дерево, вставка дубликата (решите и зафиксируйте политику), удаление листа, удаление узла с одним ребёнком, удаление корня с двумя детьми.
2. Валидация через границы. Реализуйте Valid с диапазоном и напишите тест, который ломает «наивную» валидацию: дерево, где у каждого узла локальный порядок верен, но инвариант дерева нарушен.
3. К-й по величине. Двумя способами: inorder-счётчиком (O(h + k)) и с размерами поддеревьев в узлах (O(h)). Сравните число посещённых узлов на фиксированном дереве.
4. Вырождение против баланса. Вставьте 1 000 ключей в порядке возрастания и в «случайном» порядке (фиксированный seed) — посчитайте высоту и среднее число шагов поиска в обоих деревьях. Объясните разницу числом, а не словами.
5. Замена на практике. Для задачи «курсы ищутся по коду в диапазоне» сравните два решения: отсортированный срез + sort.Search и map + сортировка при выводе. Замерьте поиск и построение на 100 000 элементов (счётчики шагов и аллокаций).

🧩 Quiz

✅ Итоги модуля

• BST даёт O(h), а не O(log n): высоту определяет порядок вставок, и отсортированный поток ключей превращает дерево в список.
• Удаление — три случая; на месте узла с двумя детьми — successor (минимум правого поддерева).
• Валидация BST передаёт диапазон вниз; локальное сравнение с родителем дыру не закрывает.
• Балансирующиеся деревья (AVL/красно-чёрные) гарантируют O(log n), но в stdlib Go их нет — и для большинства задач их роль играет отсортированный срез плюс sort.Search.
• Выбор «дерево или нет» — продуктовый: частота мутаций, диапазонные запросы, размер набора.

🔗 Мостик к Модулю 13

Мы построили иерархию по сравнениям ключей — «левое меньше, правое больше». Но есть класс задач, где иерархия задаётся символами: автокомплит по префиксу, словари, поиск подстроки в тексте. В следующем модуле — «Trie и поиск подстроки»: префиксное дерево, автокомплит за O(длины префикса) и KMP с префикс-функцией, который находит подстроку за один проход без бэктрекинга.