Структуры данных и модели вычислений
Операции с двоичным поисковым деревом
Процедура обходит все узлы поддерева с корнем в узле и печатает их ключи в неубывающем порядке:
Свойство упорядоченности гарантирует правильность алгоритма. Время работы на дереве с вершинами есть , каждая вершина обрабатывается один раз. Операторнапечатает ключи всех элементов в неубывающем порядке.
Заметим, что порядок, при котором корень предшествует узлам обоих поддеревьев, называется preorder; порядок, в котором корень следует за ними, называется postorder.
Покажем, что двоичные поисковые деревья позволяют выполнять операции,,,иза время (, где— высота дерева.
Поиск ({\rm Search)}. Процедура поиска получает на вход искомый ключ и указатель на корень дерева и возвращает указатель на вершину с ключом (если такая есть) или (если такой вершины нет).
В процессе поиска мы двигаемся от корня, сравнивая ключ с ключом, хранящимся в текущей вершине . Если они равны, поиск завершается. Если, то поиск продолжается в левом поддереве , если же, то в правом. Длина пути поиска не превосходит высоты дерева, поэтому время поиска есть(где — высота дерева).
Итеративная версия процедуры Поиск
Минимум и Максимум. Элемент с минимальным ключом в дереве поиска можно найти, пройдя от корня по указателям, пока не упремся в . Процедуравозвращает указатель на найденный элемент поддерева с корнем .
Алгоритмсимметричен:
Оба алгоритма требуют времени, где — высота дерева.
Следующий и предыдущий элементы. Если— указатель на некоторый узел дерева, то процедуравозвращает указатель на узел со следующим за элементом или, если указанный элемент — последний в дереве:
Приведенная процедура отдельно рассматривает два случая. Если правое поддерево вершины не пусто, то следующий за элемент — минимальный элемент в этом поддереве и он равен. Если правое поддерево вершиныпусто, то идем от вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Время работы процедурына дереве высоты есть , так как мы двигаемся либо только вверх, либо только вниз. Процедурасимметрична.
