Закрепление материала: Деревья поиска

Модуль "Деревья поиска" • урок 7 из 8 • ~5 минут

Суть урока. В этом модуле мы изучили двоичные деревья поиска (BST) и методы поддержания их эффективности. Деревья поиска обеспечивают логарифмическое время O(log N) для поиска, вставки и удаления, но только если они остаются сбалансированными. Мы рассмотрели АВЛ-деревья, которые строго контролируют разницу высот поддеревьев с помощью поворотов, а также деревья оптимального поиска, минимизирующие среднее время доступа при неравномерной частоте запросов.

Краткое резюме модуля

В этом модуле мы рассмотрели базовые и продвинутые концепции деревьев поиска, которые позволяют эффективно хранить и находить данные. Ниже представлены основные понятия, с которыми мы работали:

Двоичное дерево поиска (BST) - структура данных, где для любого узла все элементы левого поддерева меньше, а элементы правого - больше. Это свойство позволяет на каждом шаге отбрасывать половину вариантов.
Проблема вырождения - при добавлении отсортированных данных дерево может превратиться в линейный список, что ухудшает время поиска до O(N).
АВЛ-дерево - сбалансированное дерево, в котором для каждого узла высоты его левого и правого поддеревьев отличаются не более чем на 1.
Баланс узла - разность высот правого и левого поддеревьев. В АВЛ-дереве допустимы значения -1, 0, +1. Значения +2 или -2 сигнализируют о необходимости применить повороты.
Дерево оптимального поиска - структура, построенная с учетом вероятности запросов к ключам. Частые ключи располагаются ближе к корню для минимизации ожидаемой стоимости поиска.

Главная картина модуля: три дерева поиска и что каждое обещает

Ключевые идеи

Для обеспечения стабильной логарифмической скорости поиска и решения проблем вырождения применяются специальные механизмы:

Повороты: операции для восстановления баланса в АВЛ-дереве. При вставке узла всегда достаточно одного малого (LL/RR) или большого (LR/RL) поворота для восстановления свойства дерева.
Каскадная балансировка: при удалении узла из АВЛ-дерева общая высота поддерева может уменьшиться. Это приводит к эффекту домино и может потребовать до O(log N) поворотов вверх по дереву вплоть до корня.
Замещение при удалении: если удаляемый узел имеет двух потомков, его необходимо заменить на самый правый узел левого поддерева или на самый левый узел правого поддерева.
Оптимальность против баланса: дерево оптимального поиска может быть геометрически несбалансированным (разница высот больше 1), но при этом работать быстрее строгого АВЛ-дерева на реальных данных.

Коротко: главное

Свойство BST: левые потомки строго меньше, правые строго больше узла.
Сбалансированное дерево гарантирует время O(log N) для основных операций.
Вставка в АВЛ-дерево требует максимум одного балансирующего поворота.
Удаление из АВЛ-дерева может потребовать каскада поворотов.
Для данных с неравной частотой обращений выгоднее строить оптимальные (часто несбалансированные) деревья поиска.

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

Вопрос 1

Какой узел следует использовать для замены при удалении узла, имеющего двух потомков?

Корень левого поддерева. Самый правый элемент левого поддерева (или самый левый элемент правого поддерева). Узел, добавленный в дерево самым последним.

Вопрос 2

В чем главное отличие процесса ребалансировки АВЛ-дерева при удалении узла по сравнению со вставкой?

При удалении может потребоваться каскад из нескольких поворотов вплоть до корня, тогда как при вставке всегда достаточно одного поворота. При удалении используются совершенно другие алгоритмы поворотов, неприменимые при вставке. При удалении баланс восстанавливается автоматически без необходимости применять повороты.

Вопрос 3

Какое утверждение о деревьях оптимального поиска является верным?

Они всегда являются строго сбалансированными АВЛ-деревьями для обеспечения надежности. Они минимизируют общую высоту дерева, чтобы ускорить самый медленный возможный поиск. Они минимизируют математическое ожидание числа сравнений и могут быть геометрически несбалансированными.

Как вам урок? Спасибо за отзыв!