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

Определение

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

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

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

Search

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

Minimum

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

Maximum

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

Predecessor

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

Successor

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

Insert

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

Delete

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

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

Примерами упорядоченных множеств могут служить различные структуры данных, такие как деревья, кучи, хэш-таблицы.

Литература

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