← вся теориятеория к собесу · Алгоритмы и структуры данных

Деревья: BST, кучи и trie

Зачем это спрашивают

Деревья поиска, сбалансированные деревья и префиксные - это вопрос «что стоит за структурами твоего языка». За TreeMap в Java и std::map в C++ живёт красно-чёрное дерево, и знать это полезнее, чем уметь его писать.

Типовые формулировки: «проверь, что это корректное дерево поиска», «почему не взять кучу вместо дерева?», «как устроен автокомплит?».

// Топ-1 завал темы - проверка дерева поиска сравнением узла с родителем. Выглядит правильно, проходит на простых примерах и разваливается на первом же хитром.

Дерево поиска и его инвариант

Инвариант дерева поиска (BST, binary search tree) звучит короче, чем работает: всё левое поддерево меньше узла, всё правое больше. Ударение на слове «всё»: условие рекурсивное и держится для всех потомков, а не для одних лишь непосредственных детей.

Именно тут и живёт главная ошибка. Возьми дерево: корень 10, его левый ребёнок 5, а правый ребёнок пятёрки - 12. Проверка «узел против родителя» довольна: 12 больше 5, 5 меньше 10, всё сходится. А дерево некорректно: двенадцать сидит в левом поддереве десятки, где по инварианту не может быть ничего больше десяти. Поиск числа 12 в таком дереве пойдёт от корня направо и его не найдёт.

Правильная проверка несёт вниз диапазон допустимых значений. Корень получает неограниченный интервал (−∞, +∞); спускаясь влево, верхнюю границу заменяем на значение узла; спускаясь вправо - нижнюю. Каждый узел обязан попасть в свой интервал, и в примере выше двенадцать в интервал (−∞, 10) не попадёт.

// Поиск и вставка стоят O(h), где h - высота, то есть число уровней в самом глубоком месте дерева. Высота решает всё: у сбалансированного дерева она около log n, у выродившегося в цепочку - ровно n, и тогда никакого преимущества перед обычным списком не остаётся.

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

Балансировка: почему без неё нельзя

Обычное дерево поиска гарантий не даёт вообще. Вставь в него числа 1, 2, 3, 4, 5 по порядку - каждое окажется правее предыдущего, и вырастет не дерево, а список высотой n. Поиск станет O(n), то есть перебором. Причём отсортированные данные на вход подают постоянно, это не экзотика.

Сбалансированные деревья это чинят поворотами. Поворот - локальная перестройка двух-трёх узлов: узел опускается, его ребёнок поднимается на место родителя, поддеревья перевешиваются. Занимает константное время и, что важно, не ломает инвариант поиска - порядок значений сохраняется, меняется только форма.

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

// Полезный факт про сериализацию: одной in-order последовательности мало, чтобы восстановить дерево - форма теряется, из 1, 2, 3 можно собрать несколько разных деревьев. Сохранять надо pre-order с явными маркерами пустых мест.

Префиксное дерево и куча против дерева поиска

Trie - префиксное дерево, в котором путь от корня по буквам и есть слово. Каждое ребро помечено буквой, узлы отмечают концы слов. Слова «кот», «кола» и «код» разделят общее начало «ко» и разойдутся только там, где действительно отличаются.

Отсюда его особенность: поиск слова стоит O(длины слова) и совсем не зависит от того, сколько слов в словаре - десять или десять миллионов. Хеш-таблица так же быстра на точном совпадении, но не умеет главного: отвечать на запрос «все слова, начинающиеся на ко». Trie отвечает спуском до нужного узла и обходом поддерева, поэтому за автокомплитом и стоит он.

Куча против дерева поиска - второй дежурный вопрос. Куча даёт только экстремум, зато строится за O(n) и лежит компактным массивом. Дерево поиска держит полный порядок и потому умеет то, чего куча не умеет в принципе: диапазонные запросы, k-й по величине, ближайший больший и ближайший меньший.

// Достать «k-й минимум за O(k)», подглядывая в массив кучи, нельзя. Гарантия у кучи ровно одна - корень; про остальные элементы известно только то, что вдоль каждого пути вниз значения не убывают.

префикс: начало строки любой длины. У слова «кола» это «к», «ко», «кол» и «кола» - и все они в trie лежат на одном пути

Как отвечать: «Проверь, что бинарное дерево - корректное дерево поиска»

Несу вниз диапазон допустимых значений. Корень получает неограниченный интервал (−∞, +∞), влево спускаюсь с верхней границей, равной значению узла, вправо - с нижней, и каждый узел обязан попадать в свой интервал. Сравнивать только с непосредственным родителем - главный завал этой задачи: возьми корень 10, слева 5, а справа от пятёрки 12 - такая проверка радостно скажет, что всё в порядке, хотя двенадцать не имеет права находиться в левом поддереве десятки. Альтернативный способ - обход in-order: у корректного дерева поиска он строго возрастает, достаточно сравнивать каждый элемент с предыдущим. Обе проверки за O(n), я обычно беру диапазоны - они естественно обобщаются на задачи вроде «найди и почини сломанный узел».

Дан правильный приём, назван анти-паттерн вместе с конкретным контрпримером и предложен запасной метод. Контрпример на числах здесь решает: он показывает, что кандидат понимает, а не помнит.

На чём валят

−Проверять дерево поиска сравнением узла с родителем: нарушение через уровень проходит незамеченным.
−Ждать от обычного дерева поиска O(log n): без балансировки отсортированный вход выращивает список.
−Спорить «красно-чёрное лучше AVL» без контекста: при частом чтении выигрывает AVL, при частой записи - красно-чёрное.
−Пытаться достать k-й минимум из кучи за O(k): порядка дальше корня там нет.
−Восстанавливать дерево из одной in-order последовательности: форма теряется, нужен pre-order с маркерами пустот.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 12, остальные разбираются в тренажёре.

#tree_structures1 / 5
Как самобалансирующиеся деревья (AVL, красно-чёрные) удерживают высоту логарифмической?
A)После каждой вставки дерево целиком перестраивают в идеально сбалансированное, что и удерживает высоту логарифмической
B)Хранят элементы в массиве и сортируют его
C)Держат инвариант баланса и чинят его локальными поворотами при изменениях — высота остаётся O(log n)
D)Запрещают вставку упорядоченных данных
показать ответ и разбор
+C)Держат инвариант баланса и чинят его локальными поворотами при изменениях — высота остаётся O(log n)
// разбор: Оба типа деревьев держат структурный инвариант, гарантирующий высоту O(log n). AVL строже: |высота левого − высота правого| ≤ 1 в каждом узле — быстрее поиск, но больше поворотов при изменениях. Красно-чёрные допускают больший перекос (через правила цветов), зато дешевле в записи — их берут для часто изменяемых структур (TreeMap, планировщики). Баланс чинят локальными поворотами за O(log n), а не пересборкой.
#tree_structures2 / 5
Как бинарную кучу (heap) компактно хранят и как в массиве найти детей узла?
A)В виде связного списка узлов с явными указателями на левого и правого ребёнка, как в дереве поиска
B)В хеш-таблице по значению узла
C)В отсортированном массиве, где корень — максимум
D)В массиве без указателей: дети узла i лежат в 2i+1 и 2i+2, родитель — в (i−1)/2
показать ответ и разбор
+D)В массиве без указателей: дети узла i лежат в 2i+1 и 2i+2, родитель — в (i−1)/2
// разбор: Бинарная куча — полное дерево, поэтому её раскладывают по массиву по уровням, без указателей. Арифметика индексов заменяет ссылки: дети узла i — это 2i+1 и 2i+2, родитель — (i−1)/2. Это экономит память и даёт хорошую локальность. Куча не полностью отсортирована — гарантируется лишь свойство «родитель ≤/≥ детей», что и даёт O(1) доступ к минимуму/максимуму и O(log n) вставку/извлечение.
#tree_structures3 / 5
Для какой задачи префиксное дерево (trie) выгоднее хеш-таблицы?
A)Для точного совпадения строки-ключа: посимвольный спуск по trie обгоняет хеш-таблицу почти во всех сценариях
B)Для префиксных запросов: автодополнение, слова с началом, алфавитный порядок; стоимость — по длине ключа
C)Для хранения чисел с плавающей точкой
D)Для сжатия произвольных бинарных данных
показать ответ и разбор
+B)Для префиксных запросов: автодополнение, слова с началом, алфавитный порядок; стоимость — по длине ключа
// разбор: Trie хранит строки по символам вдоль путей, разделяя общие префиксы. Это делает его сильным там, где хеш бессилен: найти все ключи с заданным префиксом (автодополнение), перечислить слова в алфавитном порядке, искать по маске. Стоимость поиска/вставки — O(длины ключа), независимо от числа слов. Плата — память на узлы и указатели; для чистого точного поиска хеш-таблица обычно экономнее.
#tree_structures4 / 5
Чем обход дерева «в ширину» (по уровням) отличается от обходов «в глубину» и как его делают?
A)Сверху вниз по слоям через очередь (BFS); обходы в глубину идут по ветке через стек/рекурсию
B)Уровневый обход возможен только для сбалансированных деревьев
C)Это то же самое, что in-order обход
D)Способом хранения дерева: уровневый обход требует массива, а обходы в глубину — списочного представления
показать ответ и разбор
+A)Сверху вниз по слоям через очередь (BFS); обходы в глубину идут по ветке через стек/рекурсию
// разбор: Обход по уровням (level-order) — это BFS по дереву: кладём корень в очередь, затем на каждом шаге извлекаем узел и добавляем его детей в конец. Так узлы выходят слой за слоем. Обходы в глубину (pre/in/post) идут вглубь по одной ветке, используя стек или рекурсию. Выбор зависит от задачи: уровни — для «ближайших» узлов и ширины, глубина — для структуры поддеревьев.
#tree_structures5 / 5
Как в BST удаляют узел с ДВУМЯ детьми, сохраняя свойство дерева поиска?
A)Узел просто отсоединяют от родителя, а двух его детей оставляют висеть отдельными поддеревьями без связи
B)Меняют местами с корнем и удаляют корень
C)Удаляют всё поддерево целиком
D)Заменяют значением in-order преемника (минимум правого поддерева), затем удаляют тот узел — порядок цел
показать ответ и разбор
+D)Заменяют значением in-order преемника (минимум правого поддерева), затем удаляют тот узел — порядок цел
// разбор: Удаление листа или узла с одним ребёнком тривиально. Для узла с двумя детьми находят in-order преемника — минимум правого поддерева (самый левый узел там). Он гарантированно больше всего левого поддерева и меньше остального правого, поэтому его значение можно поставить на место удаляемого без нарушения порядка. У преемника нет левого ребёнка, так что его самого удаляют как простой случай.

дальше

Теорию прочитали. Навык ставится повторением

В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.

Открыть тренажёр Вся тема: Алгоритмы и структуры данных