поэтому время поиска есть 0(h) (где h - высота дерева).

Вот итеративная версия той же процедуры (которая, как правило, более эффективна):

Iterative-Tree-Search (ж, к)

1while ж ф nil и к ф кеу[х]

2do if к < кеу[х]

3then х «- left[x]

4else х right[x]

5return x

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

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

Tree-Minimum (ж)

1while left[x] ф nil

2do ж <- left[x]

3return ж

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

Tree-Maximum (ж)

1while right[x] ф nil

2do ж <- right[x]

3return ж

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

Следующий и предыдущий элементы

Как найти в двоичном дереве элемент, следующий за данным? Свойство упорядоченности позволяет сделать это, двигаясь по дереву. Вот процедура, которая возвращает указатель на следующий за ж элемент (если все ключи различны, он содержит следующий

по величине ключ) или nil, если элемент ж - последний в дереве.

Tree-Successor (ж)

1if right[x] ф nil

2then return Tree-Minimum(right[x])

3у <r- p[x]

4while у ф nil and ж = right[y]

5do ж <- у

6У <-

7return у

Процедура Tree-Successor отдельно рассматривает два случая. Если правое поддерево вершины ж непусто, то следующий за ж элемент - минимальный элемент в этом поддереве и равен Tree-Minimum(right[x]). Например, на рис. 13.2 за вершиной с ключом 15 следует вершина с ключом 17.

Пусть теперь правое поддерево вершины ж пусто. Тогда мы идём от ж вверх, пока не найдём вершину, являющуюся левым сыном своего родителя (строки 3-7). Этот родитель (если он есть) и будет искомым элементом. [Формально говоря, цикл в строках 4-6 сохраняет такое свойство: у = р[х]; искомый элемент непосредственно следует за элементами поддерева с корнем в ж.]

Время работы процедуры Tree-Successor на дереве высоты h есть 0(h), так как мы двигаемся либо только вверх, либо только вниз.

Процедура Tree-Predecessor симметрична. Таким образом, мы доказали следующую теорему.

Теорема 13.1. Операции Search, Minimum, Maximum, Successor и Predecessor на дереве высоты h выполняются за время 0(h).

Упражнения

13.2-1 Предположим, что в двоичном дереве поиска хранятся числа от 1 до 1000 и мы хотим найти число 363. Какие из следующих последовательностей не могут быть последовательностями

просматриваемых при этом ключей?

2,252,401,398,330,344, 397, 363; 924,220,911,244,898, 258, 362, 363; 925,202,911,240,912, 245, 363; 2, 399,387,219,266,382, 381, 278, 363; 935,278,347,621,299, 392, 358, 363.

13.2-2 Пусть поиск ключа в двоичном дереве завершается в листе. Рассмотрим три множества: А (элементы слева от пути попе-

ка), В (элементы на пути) и С (справа от пути). Профессор утверждает, что для любых трёх ключей а£-А, b£-Bnc£-C верно а Ь с. Покажите, что он неправ, и приведите контрпример минимально возможного размера.

13.2-3 Докажите формально правильность процедуры Tree-Successor.

13.2-4 В разделе 13.1 был построен алгоритм, печатающий все ключи в неубывающем порядке. Теперь это можно сделать иначе: найти минимальный элемент, а потом п-1 раз искать следующий элемент. Докажите, что время работы такого алгоритма есть 0(п).

13.2-5 Докажите, что к последовательных вызовов Tree-Successor выполняются за О (к + h) шагов (h - высота дерева) независимо от того, с какой вершины мы начинаем.

13.2-6 Пусть Г - двоичное дерево поиска, все ключи в котором различны, х - его лист, а у - родитель х. Покажите, что кеу[у] является соседним с кеу[х] ключом (следующим или предыдущим в смысле порядка на ключах).

13.3. Добавление и удаление элемента

Эти операции меняют дерево, сохраняя свойство упорядоченности. Как мы увидим, добавление сравнительно просто; удаление чуть сложнее.

Добавление

Процедура Tree-Insert добавляет заданный элемент в подходящее место дерева Г (сохраняя свойство упорядоченности). Параметром процедуры является указатель z на новую вершину, в которую помещены значения key[z] (добавляемое значение ключа), left[z] = nil и right[z] = nil. В ходе работы процедура меняет дерево Г и (возможно) некоторые поля вершины z, после чего новая вершина с данным значением ключа оказывается вставленной в подходящее место дерева.