Информатика · объяснение и практика

Как порядок поддеревьев определяет поиск в бинарном дереве

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

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

Сравнивайте с теми, кого уже прошли

Построим дерево с корнем 15, левым ребёнком 8 и правым 22. У узла 8 справа стоит 12. Для поиска 12 сравниваем его с 15: меньше, идём влево. Затем с 8: больше, идём вправо. Точное равенство завершает поиск. Если нужного ребёнка нет, ключ отсутствует.

Теперь попробуем вместо 12 поставить 18 справа от 8. Локально 18 больше 8, но всё левое поддерево корня должно оставаться меньше 15. Поэтому такое дерево уже не является деревом поиска. Проверка только каждой пары «родитель — ребёнок» пропустила бы эту ошибку; полезно переносить по пути допустимые нижнюю и верхнюю границы.

Пример

Узел в правом поддереве 8 и одновременно левом поддереве 15 должен иметь ключ между 8 и 15.

Каждый предок добавляет ограничение. Разрешённый диапазон является пересечением всех ограничений на пути от корня.

Почему обход даёт порядок, а вставка влияет на форму

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

Вставим последовательно 1,2,3,4 в обычное несбалансированное дерево. Каждый новый ключ уйдёт вправо, получится цепочка. Поиск 4 посетит все четыре узла. Если первым взять 3, форма окажется другой. Один и тот же набор ключей не определяет единственную форму дерева, а порядок вставки способен заметно изменить стоимость поиска.

Гарантия определяется высотой и политикой повторов

Число сравнений при поиске пропорционально высоте дерева. У сбалансированного дерева высота логарифмическая, у цепочки — линейная. Называть любой BST автоматически быстрым за логарифм нельзя: для такой гарантии нужна поддерживаемая балансировка или явно заданное условие на форму. Обычный бинарный поиск по отсортированному массиву использует другую организацию данных.

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

От чтения к действию

А теперь — вы

У корня ключ 30. В его левом поддереве находится узел 20. Какой ключ можно поставить правым ребёнком 20 при уникальных ключах?

Частые вопросы

У каждого узла обязательно два ребёнка?

Нет: бинарное означает не больше двух. Пустое поддерево и узел с одним ребёнком допустимы.

Можно ли искать по одному полю, если дерево отсортировано по другому?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться