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