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

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

Упорядоченное множество [math]Set[/math] представляет собой коллекцию элементов [math]elem[/math], каждому из которых присваивается определенный ключ [math]key[/math], отвечающий за порядок этого элемента в множестве. Бинарное отношение [math]R[/math] на упорядоченном множестве [math]Set[/math] является отношением порядка.

Вполне упорядоченным множеством, которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент.

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

Над упорядоченным множеством [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].

Примеры

• Графы;
• Пустое множество [math] \varnothing [/math];
• Множество натуральных чисел [math] \mathbb N [/math].

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
2. Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
3. Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.