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