Структуры данных и модели вычислений


Операции с двоичным поисковым деревом


Процедура обходит все узлы поддерева с корнем в узле и печатает их ключи в неубывающем порядке:

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

Заметим, что порядок, при котором корень предшествует узлам обоих поддеревьев, называется preorder; порядок, в котором корень следует за ними, называется postorder.

Покажем, что двоичные поисковые деревья позволяют выполнять операции,,,иза время (, где— высота дерева.

Поиск ({\rm Search)}. Процедура поиска получает на вход искомый ключ и указатель на корень дерева и возвращает указатель на вершину с ключом (если такая есть) или (если такой вершины нет).

В процессе поиска мы двигаемся от корня, сравнивая ключ с ключом, хранящимся в текущей вершине . Если они равны, поиск завершается. Если, то поиск продолжается в левом поддереве , если же, то в правом. Длина пути поиска не превосходит высоты дерева, поэтому время поиска есть(где — высота дерева).

Итеративная версия процедуры Поиск

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

Алгоритмсимметричен:

Оба алгоритма требуют времени, где — высота дерева.

Следующий и предыдущий элементы. Если— указатель на некоторый узел дерева, то процедуравозвращает указатель на узел со следующим за элементом или, если указанный элемент — последний в дереве:

Приведенная процедура отдельно рассматривает два случая. Если правое поддерево вершины не пусто, то следующий за элемент — минимальный элемент в этом поддереве и он равен. Если правое поддерево вершиныпусто, то идем от вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Время работы процедурына дереве высоты есть , так как мы двигаемся либо только вверх, либо только вниз. Процедурасимметрична.




Начало  Назад  Вперед



Книжный магазин