Упорядоченное множество

Пример сбалансированного множества:

Сбалансированное дерево, т.е. то дерево, в котором высота его поддеревьев различается не более чем на 1цу.

Операции над упорядоченным множеством

Чтобы работать со множеством было проще - используют упорядоченное множество, где можно совершать следующие операции: [math]Search(x)[/math] (поиск), [math]Minimum[/math] (минимум), [math]Maximum[/math] (максимум), [math]Predecessor[/math] (предыдущий), [math]Successor[/math] (следующий), [math]Insert(x)[/math] (вставить), и [math]Delete(x)[/math] (удалить).

Search

Процедура поиска получает на вход искомый ключ [math]x[/math], и возвращает указатель на элемент множества или специальное значение [math]NIL[/math], если такого элемента нет.

Minimum

Процедура [math]Minimum[/math] возвращает указатель на минимальный элемент множества.

Maximum

Процедура [math]Maximum[/math] возвращает указатель на максимальный элемент множества.

Predecessor

Процедура [math]Predecessor[/math] возвращает указатель на предыдущий элемент множества.

Successor

Процедура [math]Successor[/math] возвращает указатель на следующий элемент множества.

Insert

Процедура [math]Insert(x)[/math] добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности).

Delete

Параметром процедуры [math]Delete(x)[/math] удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности).

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5