Зачем нужны самобалансирующиеся деревья

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

Понимаете ли вы, откуда берётся гарантия O(log n) и почему её нет у простого двоичного дерева поиска. Для Java-разработчика следом почти всегда идёт вопрос, где такие деревья спрятаны в JDK: в TreeMap и внутри HashMap.

Как отвечать

Начните с проблемы. Обычное двоичное дерево поиска держит O(log n) только при случайном порядке вставки. Если вставлять уже отсортированные ключи, каждый новый узел уходит вправо, дерево вырождается в список, и поиск становится O(n).

Самобалансирующееся дерево после вставки и удаления восстанавливает ограничение на высоту поворотами узлов, поэтому поиск, вставка и удаление остаются O(log n) в худшем случае, а не только в среднем.

• AVL-дерево: высоты поддеревьев любого узла отличаются не больше чем на единицу. Дерево ниже, поиск чуть быстрее, но при изменениях поворотов больше;
• красно-чёрное дерево: баланс мягче, высота не больше примерно 2·log n, зато вставка требует не больше двух поворотов, а удаление не больше трёх. Хороший компромисс при частой записи;
• B-дерево и B+-дерево: не двоичные, узел хранит много ключей и занимает страницу диска. На них построены индексы баз данных.

Где это в Java:

• TreeMap и TreeSet: красно-чёрное дерево. Дают порядок ключей и операции, которых нет у HashMap: floorKey(), ceilingKey(), headMap(), subMap();
• HashMap с Java 8: если в одной корзине становится больше восьми элементов, а таблица уже не меньше 64, цепочка превращается в красно-чёрное дерево. Это защищает от атаки коллизиями, при которой поиск деградирует до O(n).

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

Говорят, что сбалансированное дерево быстрее хэш-таблицы. Поиск по ключу в хэш-таблице в среднем O(1), дерево выбирают ради порядка и диапазонных запросов.

Путают AVL и красно-чёрное дерево или не могут сказать, почему в JDK выбрано второе: меньше перестроек при записи.

Забывают, что TreeMap сравнивает ключи через compareTo() или Comparator, а не через equals(). Если сравнение с ним не согласовано, два разных объекта окажутся одним ключом.