Как происходит балансировка дерева после вставке элемента

Что проверяют

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

Как отвечать

Сначала вставка идёт как в обычном дереве поиска: спускаемся от корня, сравниваем ключ, добавляем лист. Дальше всё зависит от вида дерева.

AVL-дерево хранит в узле высоту. На обратном пути от нового листа к корню пересчитываем высоту и баланс, то есть разность высот левого и правого поддерева. Если баланс стал 2 или минус 2, возможны четыре случая:

• LL: новый ключ в левом поддереве левого сына. Лечится правым поворотом;
• RR: зеркально, левый поворот;
• LR: новый ключ в правом поддереве левого сына. Сначала левый поворот у сына, потом правый у узла;
• RL: зеркально LR.

Важная деталь: после вставки хватает одного одинарного или двойного поворота, высота поддерева возвращается к прежней, и выше подниматься уже не нужно.

Красно-чёрное дерево вставляет узел красным. Если родитель тоже красный, свойство нарушено: при красном дяде перекрашиваем родителя, дядю и деда и продолжаем с деда, при чёрном дяде делаем один или два поворота и перекраску. Поворотов не больше двух, корень в конце красится в чёрный.

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

Про Go: сбалансированного дерева в стандартной библиотеке нет, map это хеш-таблица без порядка. Для упорядоченных данных берут отсортированный срез с slices.BinarySearch или sort.Search, либо сторонний пакет с B-деревом.

Где спотыкаются

Пересчитывают высоты в повороте в неправильном порядке. Сначала обновляется узел, который опустился вниз, потом новый корень поддерева.

Считают, что балансировка после вставки делает O(log n) поворотов. Подъём по дереву логарифмический, а поворотов при вставке константа.

Говорят, что map в Go устроен как дерево и обходится по порядку ключей. Порядок обхода map намеренно случайный.