Минимум и максимум

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

Листинг 3.26 – Процедура поиска минимального элемента в двоичном дереве поиска

Свойство упорядоченности гарантирует правильность процедуры

Tree- Minimum. Если у вершины х нет левого ребёнка, то минимальный элемент поддерева с корнем х есть х, так как любой ключ в правом поддереве не меньше key[x]. Если же левое поддерево вершины х не пусто, то минимальный элемент поддерева с корнем х находится в этом левом поддереве (поскольку сам х и все элементы правого поддерева больше).

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

Листинг 3.27 – Процедура поиска максимального элемента в двоичном дереве поиска

Оба алгоритма требуют времени O(h), где h — высота дерева (поскольку двигаются по дереву только вниз).