Какие полезные свойства имеет красно-черное дерево и почему оно используется
Что проверяют
Понимаете ли вы, зачем нужна балансировка, и отличаете ли гарантии структуры от её внутренней механики. Следом почти всегда спрашивают, чем красно-черное дерево лучше AVL и где оно спрятано в JDK.
Как отвечать
Начните с инварианта, а не с перечисления цветов: смысл раскраски в том, чтобы длиннейший путь от корня до листа был не более чем вдвое длиннее короткого.
- свойства: узел красный или черный; корень черный; у красного узла оба ребёнка черные, то есть двух красных подряд не бывает; на всех путях от узла до NIL-листьев одинаковое число черных узлов;
- следствие: высота не превышает
2*log2(n+1), поэтому поиск, вставка и удаление это O(log n) в худшем случае, а не только в среднем; - починка: после вставки хватает не более двух поворотов, после удаления не более трёх, остальное это перекраска. Вся операция укладывается в O(log n);
- порядок: это дерево поиска, значит обход даёт отсортированную последовательность, работают запросы по диапазону и операции вида
floorKeyиceilingKey.
Дальше сравнение. AVL держит баланс жёстче (разница высот поддеревьев не больше единицы), поэтому ищет чуть быстрее, но платит большим числом поворотов при записи. Красно-черное дерево перебалансируется реже, и это выгоднее там, где вставок и удалений много.
Где это в Java: TreeMap и TreeSet, а также корзины HashMap. При восьми коллизиях в одной корзине связный список превращается в красно-черное дерево, и поиск в корзине деградирует до O(log n) вместо O(n). В ядре Linux на нём стоят планировщик и учёт областей памяти.
Где спотыкаются
Заучивают пять свойств и не могут сказать, что из них следует. Интервьюеру нужна связь: запрет двух красных подряд плюс равное число черных на путях и даёт ограничение высоты.
Путают с B-деревом и заявляют, что красно-черные деревья лежат в индексах баз данных. На диске выигрывает B+ дерево: у него узел размером со страницу и высокий фактор ветвления, а бинарное дерево дало бы слишком много случайных чтений.
Говорят «O(log n) в среднем». В том и ценность структуры, что это оценка худшего случая, в отличие от обычного BST, который на отсортированной вставке вырождается в список.