Как происходит балансировка дерева после вставки элемента
Что проверяют
Понимаете ли вы, как сбалансированное дерево удерживает высоту O(log n), и знаете ли, где это живёт в JDK. Следом спрашивают, какое дерево внутри TreeMap и что происходит с корзиной HashMap при большом числе коллизий.
Как отвечать
Сначала обычная вставка в дерево поиска, затем восстановление инварианта. Для Java главный пример это красно-чёрное дерево, на нём построены TreeMap и TreeSet. Его свойства:
- цвет: каждый узел красный или чёрный, корень чёрный, пустые листья считаются чёрными;
- нет двух красных подряд: у красного узла оба сына чёрные;
- чёрная высота: на любом пути от узла до листьев одинаковое число чёрных узлов. Отсюда высота не больше 2·log2(n+1).
Новый узел вставляется красным. Нарушиться может только правило двух красных, если родитель тоже красный. Дальше смотрим на дядю:
- дядя красный: перекрашиваем родителя и дядю в чёрный, деда в красный и продолжаем проверку с деда;
- дядя чёрный, узел «внутренний»: поворот вокруг родителя сводит ситуацию к внешнему случаю;
- дядя чёрный, узел «внешний»: поворот вокруг деда и обмен цветами родителя и деда.
В конце корень красится в чёрный. Поворотов при вставке не больше двух. В JDK это метод fixAfterInsertion в TreeMap.
AVL держит разницу высот поддеревьев в пределах единицы: оно ниже и быстрее на поиске, но при удалении может поворачивать на каждом уровне.
Про HashMap: с Java 8 цепочка в корзине превращается в красно-чёрное дерево, когда её длина превышает TREEIFY_THRESHOLD (8), а таблица не меньше 64 ячеек. Обратно в список дерево сворачивается, если после расширения таблицы в корзине остаётся не больше UNTREEIFY_THRESHOLD (6) элементов. Это страхует от деградации до O(n) при плохом hashCode.
Где спотыкаются
Называют TreeMap AVL-деревом. В JDK это красно-чёрное дерево, что указано в документации класса.
Забывают про минимальную ёмкость 64. Если таблица меньше, при переполнении корзины HashMap сначала расширяется, а не строит дерево.
Знают повороты, но не объясняют, зачем вставлять узел красным. Чёрный узел сразу сломал бы чёрную высоту на всех путях через него, а красный ломает только локальное правило.