Какие способы балансировки деревьев существуют
Что проверяют
Знаете ли вы, зачем дереву балансировка и чем схемы отличаются по цене вставки и поиска. Для Java-разработчика следом почти всегда идёт вопрос, какое дерево внутри TreeMap и когда HashMap превращает корзину в дерево.
Как отвечать
Начните с сути: обычное BST при вставке отсортированных ключей вырождается в список, и операции становятся O(n). Балансировка держит высоту O(log n). Основные схемы:
- AVL-дерево: высоты поддеревьев любого узла отличаются не больше чем на 1. Высота около 1,44·log₂n, поэтому поиск чуть быстрее. Вставке хватает одного одинарного или двойного поворота, а удаление может запускать повороты до самого корня;
- красно-чёрное дерево: правила раскраски, высота не больше 2·log₂(n+1). Вставка обходится максимум двумя поворотами, удаление тремя, остальное перекраска. Это дерево внутри
TreeMapиTreeSet; - splay-дерево: поднимает использованный узел в корень. Амортизированно O(log n), отдельная операция может стоить O(n), зато частые ключи всегда рядом;
- декартово дерево (treap): ключ по правилам BST, случайный приоритет по правилам кучи. Ожидаемая высота O(log n), реализация короткая через
splitиmerge; - B-дерево и B+-дерево: много ключей в узле, размер узла под страницу диска. Основа индексов в базах и файловых системах.
Привяжите к Java: в HashMap с Java 8 корзина превращается в красно-чёрное дерево, когда в ней 8 элементов и ёмкость таблицы не меньше 64, а при ресайзе дерево из 6 и менее узлов возвращается в список. ConcurrentSkipListMap построен на skip list, а не на дереве: так проще обойтись без глобальных блокировок.
Где спотыкаются
Говорят, что корзина HashMap становится деревом сразу при восьми элементах. Если таблица меньше 64, HashMap сначала увеличивает её, а дерево не строит.
Путают BST с кучей или не могут нарисовать поворот. Интервьюер часто просит повернуть три узла на доске, и это проверяет понимание лучше перечня названий.
Утверждают, что AVL медленнее на вставке из-за множества поворотов. На вставке их не больше двух, разница с красно-чёрным деревом в основном на удалении, а при частом чтении AVL даже выгоднее.