EssayAI
Блог
Блог
Естественные науки

Дерево двоичного поиска: построение и операции

8 ноября 2026Время чтения: 8 минут
#дерево двоичного поиска#структуры данных#BST#обход дерева#алгоритмы
Дерево двоичного поиска: построение и операции

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

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

Из чего состоит дерево

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

Слово «двоичное» означает не двоичную запись числа, а максимум двух детей у каждого узла. Упорядоченность при этом распространяется на всё поддерево, а не только на непосредственных детей. Например, если корень равен 8, а левый ребёнок равен 3, число 9 нельзя поставить справа от 3: оно больше 3, но остаётся в левом поддереве 8.

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

Как построить дерево вставкой

Начнём с пустой структуры и последовательно вставим ключи 8, 3, 10, 1, 6, 14, 4, 7, 13. Первый ключ 8 становится корнем. Следующий меньше 8 и занимает свободную левую ссылку; 10 больше 8 и идёт вправо. Затем 1 оказывается слева от 3, а 6 - справа от него. Ключ 14 становится правым ребёнком 10.

Для 4 путь проходит через 8 и 3: сначала влево, затем вправо к 6, затем влево. Аналогично 7 занимает место справа от 6, а 13 - слева от 14. На каждом шаге новая вершина добавляется только в пустую ссылку, так что существующие ключи не перемещаются.

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

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

Минимум, максимум и обход по порядку

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

Симметричный обход посещает сначала левое поддерево, затем сам узел и наконец правое поддерево. Применяя правило рекурсивно, для нашего дерева получаем последовательность 1, 3, 4, 6, 7, 8, 10, 13, 14. Она отсортирована, потому что перед каждым узлом выводятся меньшие ключи его поддерева, а после него - большие. Обойти все nn узлов нужно за O(n)O(n) времени; рекурсивный стек в худшем случае занимает O(h+1)O(h+1), где hh - высота в рёбрах.

Другие порядки полезны для других задач: прямой обход сначала посещает узел, затем его поддеревья; обратный - узел после обоих поддеревьев. Сам по себе список обхода не заменяет описание структуры. Связь между высотой, уровнями и числом вершин подробнее разобрана в статье о высоте и глубине дерева.

Удаление: три случая

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

  1. Нет детей. Лист просто отсоединяют от родителя. Например, удаление 7 не затрагивает остальные узлы.
  2. Один ребёнок. Ссылку родителя перенаправляют на единственного ребёнка. Если удалить 14 из исходного примера, его место справа от 10 займёт 13.
  3. Два ребёнка. Ключ заменяют ближайшим следующим по порядку ключом - минимумом правого поддерева - и удаляют этот ключ из прежнего места. Вместо него можно аналогично использовать максимум левого поддерева.

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

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

Почему форма влияет на сложность

Примем высоту hh равной числу рёбер на самом длинном пути от корня к листу; высота дерева из одного узла тогда равна нулю. В примере самый длинный путь, например 8 → 3 → 6 → 4, содержит три ребра. Вставка, поиск и стандартное удаление проходят путь длиной не больше нескольких величин порядка h+1h+1, поэтому их худшее время для конкретного дерева - O(h+1)O(h+1). Подробный разбор сравнений дан в статье о поиске в BST.

Для семи ключей 1–7 последовательность 4, 2, 6, 1, 3, 5, 7 даёт высоту 2. Вставка тех же ключей по возрастанию даёт цепочку высоты 6: каждый следующий ключ становится правым ребёнком предыдущего. На схеме показаны обе формы.

Два дерева из ключей от 1 до 7: разветвлённое высотой 2 и цепочка высотой 6 рёбер
Два дерева из ключей от 1 до 7: разветвлённое высотой 2 и цепочка высотой 6 рёбер

При высоте O(log⁡n)O(\log n) основные операции выполняются за O(log⁡n)O(\log n); при высоте n−1n-1 они могут потребовать O(n)O(n). Свойство BST само по себе не гарантирует логарифмическую высоту. Например, AVL-дерево поддерживает дополнительные ограничения и использует повороты, чтобы контролировать высоту. B-дерево решает похожую задачу для узлов с большим числом ключей и детей.

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

После вставки полезно выполнить две независимые проверки. Сначала проследите путь каждого ключа от корня и выпишите ограничения, полученные на поворотах. Для ключа 4 путь через 8, 3 и 6 задаёт одновременно условия: меньше 8, больше 3 и меньше 6. Все три выполнены. Для вымышленного ключа 9 на том же месте первое условие нарушится, даже если сравнение с ближайшим родителем выглядит допустимым.

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

Где структура полезна

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

Не стоит путать BST с двоичной кучей. В куче упорядочены отношения родителя и детей, что удобно для доступа к экстремуму; общее правило «всё слева меньше, всё справа больше» для неё не требуется. Поэтому выбор структуры зависит от нужных операций, а не только от сходства рисунков.

Частые ошибки

  • Проверять только непосредственных детей и забывать ограничения от предков.
  • Считать, что любое BST автоматически сбалансировано и всегда работает за O(log⁡n)O(\log n).
  • При удалении узла с двумя детьми копировать случайный ключ из правого поддерева вместо его минимума.
  • Путать высоту в рёбрах с числом узлов на пути: в цепочке из семи узлов это 6 и 7 соответственно.
  • Не оговаривать обработку равных ключей: разные реализации могут хранить их по-разному.

FAQ

Обязательно ли дерево должно быть полным?

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

Можно ли восстановить форму по отсортированному обходу?

Нет. Любые корректные BST с одним набором различных ключей дадут одинаковый симметричный обход, хотя их форма и высота могут различаться.

Как проверить, что рисунок является BST?

Рекурсивно проверяйте допустимый интервал каждого узла, сужая его при каждом спуске. Для уникальных ключей границы строгие. Одного сравнения с родителем недостаточно.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева: порядки и примеры

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

8 ноября 20268 минут
Односвязный список: операции и их сложность

Односвязный список: операции и их сложность

Односвязный список: как устроены узлы и ссылки, как выполнять поиск, вставку и удаление, сколько переходов они требуют и когда нужен указатель на хвост.

8 ноября 20269 минут
Префиксное дерево: как устроен бор строк

Префиксное дерево: как устроен бор строк

Префиксное дерево хранит общие начала строк вместе. Разбираем построение бора, поиск и удаление слов, сложность операций и применение на наглядном примере.

8 ноября 20268 минут
Сортировка слиянием: как работает merge sort

Сортировка слиянием: как работает merge sort

Сортировка слиянием на примере массива: разбор проходов и числа сравнений, устойчивость, оценка времени и памяти, реализация на Python и области применения.

8 ноября 20268 минут
Сортировка связного списка слиянием: алгоритм

Сортировка связного списка слиянием: алгоритм

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

8 ноября 20269 минут
Дерево Фенвика: суммы и обновления по шагам

Дерево Фенвика: суммы и обновления по шагам

Дерево Фенвика хранит суммы блоков массива и помогает быстро отвечать на запросы и менять элементы. Разбираем lowbit, пример вычислений, реализацию на Python и сложность операций.

8 ноября 20269 минут