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

Определение:

Упорядоченное множество представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве.

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

Над упорядоченным множеством [math]Set[/math] заданы следующие операции:

Insert

Функция [math]\mathrm {insert(Set, elem, elemKey)}[/math] добавляет заданный элемент [math]elem[/math], имеющий ключ [math]elemKey[/math], в подходящее место множества [math]Set[/math] (сохраняя свойство упорядоченности).

Delete

Функция [math]\mathrm {delete(Set, key)}[/math] удаляет элемент, имеющий ключ [math]key[/math] (сохраняя свойство упорядоченности).

Search

Функция [math]\mathrm {search(Set, key)}[/math], которая получает на вход искомый ключ [math]key[/math], и возвращает указатель на элемент множества [math]Set[/math] или специальное значение [math]null[/math], если такого элемента нет.

Minimum

Функция [math]\mathrm {minimum(Set)}[/math] возвращает указатель на минимальный элемент множества [math]Set[/math].

Maximum

Функция [math]\mathrm {maximum(Set)}[/math] возвращает указатель на максимальный элемент множества [math]Set[/math].

Predecessor

Функция [math]\mathrm {predecessor(Set, elem)}[/math] возвращает указатель на элемент, стоящий перед элементом [math]elem[/math] множества [math]Set[/math].

Successor

Функция [math]\mathrm {successor(Set, elem)}[/math] возвращает указатель на элемент, стоящий после элемента [math]elem[/math] множества [math]Set[/math].

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

Примерами упорядоченных множеств могут служить такие структуры как деревья.

Литература

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