Какова роль раскраски узлов в красно-черном дереве
Что проверяют
Понимаете ли вы, что цвет узла это компактный способ хранить информацию о балансе, и как из правил раскраски следует логарифмическая высота. Для Java-разработчика следом почти всегда идёт вопрос, где это дерево живёт в JDK.
Как отвечать
Сначала правила:
- два цвета: каждый узел красный или чёрный, корень всегда чёрный;
- листья: пустые ссылки NIL считаются чёрными узлами;
- красное правило: у красного узла оба потомка чёрные, двух красных подряд не бывает;
- чёрная высота: на любом пути от узла вниз до листьев одинаковое число чёрных узлов.
Из последних двух правил следует главное: самый длинный путь (красные и чёрные вперемешку) не более чем вдвое длиннее самого короткого (только чёрные). Отсюда высота не больше 2·log2(n+1) и гарантированные O(log n) на поиск, вставку и удаление.
Раскраска заменяет точное хранение высоты: на узел нужен один бит, а баланс держится приблизительно. Новый узел красят в красный, так чёрная высота не меняется и может сломаться только красное правило. Если дядя красный, хватает перекраски, и проблема поднимается выше; если чёрный, делают один или два поворота. Вставка требует не больше двух поворотов, удаление не больше трёх.
В JDK это TreeMap и построенный на нём TreeSet, цвет там хранится полем boolean color. С Java 8 HashMap превращает корзину в такое же дерево, когда в ней больше 8 элементов, а таблица не меньше 64 ячеек. AVL сбалансировано строже и ищет чуть быстрее, но чаще вращается при записи.
Где спотыкаются
Говорят, что красно-чёрное дерево идеально сбалансировано. Оно сбалансировано приблизительно, пути отличаются до двух раз, и в этом весь смысл: меньше перестроек при записи.
Забывают правило чёрной высоты. Без него раскраска ничего не гарантирует: цепочка из одних чёрных узлов формально не нарушает красное правило, но это уже список.
Утверждают, что HashMap хранит корзины деревом с первой коллизии. Дерево появляется только при длинной цепочке и достаточном размере таблицы, а ключам желательно быть Comparable, иначе порядок внутри дерева строится по System.identityHashCode, и поиск теряет часть выгоды.