Деревья поиска: инвариант, высота и баланс

Каталог часто получает новые ключи. Отсортированный массив быстро ищет нужное место, но вставка сдвигает хвост. Дерево поиска хранит порядок в связях между узлами, поэтому стоимость зависит от длины пути от корня.

Правило дерева поиска

В этой главе каждый целочисленный ключ хранится один раз. Для узла с ключом x все ключи левого поддерева меньше x, все правого — больше x. Это глобальное условие на поддеревья, а не только сравнение двух непосредственных детей.

type Node struct {
    Key int
    Left, Right *Node
}
func Contains(n *Node, key int) bool {
    for n != nil {
        if key == n.Key { return true }
        if key < n.Key { n = n.Left } else { n = n.Right }
    }
    return false
}

На каждом шаге одно поддерево исключается по инварианту. Отсутствие узла означает отсутствие ключа на выбранном пути. Время O(h), где h — высота дерева; дополнительная память цикла O(1). Запись O(log n) пока не обоснована: высота может оказаться n.

Вставка и форма

Начните с пустого дерева и вставьте 4,2,6,1,3. Корень 4, слева 2 с детьми 1 и 3, справа 6. При вставке выбирайте тот же путь, что при поиске; на месте nil создавайте новый узел. Повторный ключ по нашему договору ничего не меняет.

Теперь вставьте в пустое дерево 1,2,3,4,5. Получится цепочка правых детей. Найти 5 нужно за пять посещений. Случайно перемешанный вход часто улучшает ожидаемую высоту, но это не гарантия для любого входа.

Сбалансированные деревья поддерживают дополнительные ограничения формы. AVL ограничивает разность высот поддеревьев, red-black tree поддерживает правила окраски. Поворот меняет связи нескольких узлов, сохраняя порядок ключей. Вы не обязаны реализовать все варианты в первом курсе, но должны понимать, откуда появляется обещание логарифмической высоты.

Обход не равен поиску

Обход inorder сначала посещает левое поддерево, затем узел, затем правое. По правилу дерева результат отсортирован. Он посещает все n узлов: время O(n). Рекурсивный стек имеет O(h) глубины. Если при каждом узле склеивать новые массивы неаккуратно, реализация может добавить копирования сверх O(n); простой накопитель, передаваемый по ссылке, делает цену явной.

В reference.InOrder используется один общий накопитель, поэтому каждый ключ добавляется ровно один раз. Попробуйте альтернативу с отдельными срезами поддеревьев: повторное копирование при склейке может дать квадратичную работу на цепочке. Сравните -benchmem и объясните источник различия.

Удаление требует сохранить всё поддерево

Лист можно отсоединить. Узел с одним ребёнком заменяется этим ребёнком. Узел с двумя детьми обычно заменяют следующим по порядку ключом: минимумом правого поддерева, затем удаляют тот прежний узел. Просто занулить Left или Right потеряет другие значения. При работе с указателями нужно обновлять связь родителя, а иногда и корень.

Самостоятельная практика

Реализуйте Insert и Contains, затем inorder с общим накопителем. Проверьте порядок из примера, повтор ключа и пустое дерево. Отдельно реализуйте проверку глобального инварианта через допустимые нижнюю и верхнюю границы.

Контрпример для проверки только детей: корень 10, слева 5, а правый ребёнок узла 5 имеет ключ 12. Связь 5→12 локально допустима, но всё левое поддерево корня должно быть меньше 10. Ваш валидатор должен отвергнуть это дерево. Практика — 55 минут.

Критерии готовности: ключи не теряются; повторы соответствуют договору; оценка дана через h; валидатор проверяет поддеревья; пустой корень обработан.

Разбор

Для теста структуры достаточно проверить inorder на ожидаемое множество и отдельно глобальное условие. Отсортированный обход сам по себе не показывает, что высота мала. Сравните высоты дерева после отсортированных и перемешанных вставок; не превращайте один эксперимент в гарантию случайной балансировки.

Источники: Princeton: binary search trees, balanced search trees.