Что такое сбалансированное дерево
Что проверяют
Понимаете ли вы, зачем нужна балансировка, и знаете ли конкретные разновидности.
Как отвечать
Сбалансированное дерево поиска это дерево, которое само поддерживает малую высоту при вставках и удалениях, гарантируя логарифмическую сложность операций.
Зачем это нужно, лучше объяснить от обратного. Обычное дерево поиска не даёт никаких гарантий: если вставлять уже упорядоченные данные, каждый новый элемент окажется справа, и дерево выродится в связный список. Поиск станет линейным, то есть вся выгода структуры исчезнет. А упорядоченные данные на входе это не редкий случай, а типичный: идентификаторы, даты, время создания.
Балансировка решает эту проблему: после каждой модификации дерево проверяет условие и при необходимости выполняет повороты, локальные перестроения, восстанавливающие форму.
Основные разновидности:
- AVL-дерево: строгое условие, высоты поддеревьев различаются не более чем на единицу. Дерево получается ниже, поиск быстрее, но перебалансировок при изменениях больше;
- красно-чёрное дерево: условие слабее, дерево может быть выше примерно вдвое, зато изменения дешевле. Именно поэтому его выбирают для универсальных упорядоченных коллекций в стандартных библиотеках языков;
- B-дерево и его вариант с данными в листьях: узел вмещает много ключей и равен странице диска. Это выбор для индексов баз данных, где стоимость измеряется не сравнениями, а обращениями к диску;
- дерево с пропусками: вероятностная альтернатива, где балансировка достигается случайными уровнями. Проще реализуется и хорошо работает при конкурентном доступе.
Что даёт балансировка помимо скорости поиска: упорядоченность позволяет делать запросы по диапазону, находить ближайший элемент и обходить данные по возрастанию. Хеш-таблица при своей постоянной сложности ничего этого не умеет.
Где спотыкаются
Не могут объяснить, почему обычное дерево поиска вырождается.
Не знают ни одной конкретной разновидности.
Считают, что хеш-таблица всегда лучше из-за постоянного времени.
Путают балансировку по высоте с равным числом узлов в поддеревьях.