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

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

Упорядоченное множество [math]Set[/math] представляет собой коллекцию элементов [math]elem[/math], каждому из которых присваивается определенный ключ [math]key[/math], отвечающий за порядок этого элемента в множестве. Бинарное отношение [math]R[/math] на упорядоченном множестве [math]Set[/math] обладает следующими свойствами: Антисимметричность: [math]\mathcal {8} x,y \in A \ (xRy \land yRx \Rightarrow x = y)[/math]; Транзитивность: [math]\mathcal {8} x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)[/math].

Пустое множество [math] \varnothing [/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].

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

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

Литература

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