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

Пример упорядоченного множества:

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

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

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

Search

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

Minimum

Функция Minimum возвращает указатель на минимальный элемент множества.

Maximum

Функция Maximum возвращает указатель на максимальный элемент множества.

Predecessor

Функция Predecessor возвращает указатель на предыдущий элемент множества.

Successor

Функция Successor возвращает указатель на следующий элемент множества.

Insert

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

Delete

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

Литература

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