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

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

Листинг 3.28 – Процедура поиска следующего (в смысле порядка на ключах) элемента в двоичном дереве поиска

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

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

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

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

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