Что такое самобалансирующиеся деревья, например красно-черное дерево

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

Понимаете ли, зачем дереву балансировка, и связываете ли теорию со стандартной библиотекой. От Java-кандидата ждут не пересказа свойств, а объяснения, откуда берётся гарантия логарифма и где он с этим деревом уже работал.

Как отвечать

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

Красно-чёрное дерево держит баланс не строго, а через набор инвариантов: у каждого узла есть цвет, корень чёрный, листовые пустые узлы считаются чёрными, у красного узла оба потомка чёрные, и на всех путях от узла до листьев одинаковое число чёрных узлов. Отсюда следует ключевое: самый длинный путь не длиннее удвоенного самого короткого. Вставка идёт как в обычном дереве поиска, дальше перекраска и повороты восстанавливают инварианты.

Сравнение с AVL: AVL держит баланс строже, поиск в нём чуть быстрее, но перестроений при записи больше. Красно-чёрное дешевле на изменениях, поэтому его выбирают для контейнеров общего назначения. В Java на нём построены TreeMap и TreeSet, и на него же HashMap переводит слишком длинную цепочку в корзине, чтобы худший случай при плохих хэшах был логарифмическим, а не линейным.

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

Заучивают пять свойств и не могут сказать, что из них следует. Свойства это средство, а цель одна: ограничить высоту, чтобы операции не деградировали. Без этой связки ответ звучит как цитата.

Путают семейства структур. Куча даёт быстрый минимум, но не упорядоченный обход; B-дерево решает другую задачу, оно оптимизирует число чтений страниц с диска, поэтому живёт в базах, а не в оперативных коллекциях.

Считают TreeMap более быстрой заменой HashMap. Хэш-таблица даёт доступ за константу, дерево за логарифм, и упорядоченную структуру берут ради сортированного обхода, диапазонных запросов и методов вроде floorKey, а не ради скорости.