Изменения

{{Определение|definition ='''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве.}}Бинарное отношение на упорядоченном множестве является [[отношение порядка|отношением порядка]].

==Операции над '''Вполне упорядоченным множеством==Над упорядоченным множеством <tex>Set</tex> заданы следующие операции:=== Insert ===Функция <tex>\mathrm {insert(Set''', которое явяется важнейшим частным случаем, elemназывается упорядоченное множество, elemKey)}</tex> добавляет заданный каждое непустое подмножество которого содержит минимальный элемент <tex>elem</tex>, имеющий ключ <tex>elemKey</tex>, в подходящее место множества <tex>Set</tex> (сохраняя свойство упорядоченности).

=== Delete =Операции над упорядоченным множеством ==Функция Над упорядоченным множеством <tex>set</tex> заданы следующие операции:* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {delete(Setset, keyelem)}</tex> {{---}} удаляет элемент, имеющий ключ <tex>keyelem</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает <tex>true</tex> при наличии элемента в множестве или <tex>false</tex> в противном случае,* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,* <tex>\mathrm {predecessor(set, elem)}</tex> {{---}} возвращает элемент, стоящий перед элементом <tex>elem</tex> множества <tex>set</tex>.* <tex>\mathrm {successor(set, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>.

=== Search =Наивная реализация на массиве ==Функция Упорядоченное множество <tex>\mathrm {search(Set, key)}s</tex>, которая получает на вход искомый ключ содержащее <tex>keyn</tex>элементов, и возвращает указатель на элемент множества <tex>Setможно реализовать с помощью [[Сортировки | отсортированного]] массива </tex> или специальное значение <tex>nullelements[0..n-1]</tex>, если такого элемента нет.

=== Minimum ===Функция <tex>\mathrm {minimum(Set)}</tex> возвращает указатель Рассмотрим реализацию на минимальный элемент множества <tex>Set</tex>примере отсортированного по возрастанию целочисленного массива.

<code> '''struct''' Set<T>: '''int''' n <font color=green>// количество элементов множества</font color== Maximum ===green>Функция '''T'''[n] elements <texfont color=green>\mathrm {maximum(Set)}</tex> возвращает указатель на максимальный элемент / массив элементов множества типа ''T''<tex/font color=green>Set</texcode>.

=== Predecessor '''insert''' ===Функция <texcode>\mathrm {predecessor '''func''' insert(Set<T> s, T elem)}: s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</texfont color=green> <font color=green> возвращает указатель // увеличиваем размер массива с элементами множества на элементединицу.</font color=green> s.elements[s.n - 1] = elem <font color=green>// Вставляем ''elem'' в конец массива</font color=green> '''int''' i = s.n - 1 '''while''' s.elements[i] < s.elements[i - 1] <font color=green>// Сортируем массив,</font color=green> swap(s.elements[i], стоящий перед элементом s.elements[i - 1]) <texfont color=green>// пока ''elem'' не окажется в нужном месте.</font color=green></texcode> множества Время выполнения {{---}} <tex>SetO(n)</tex>.

=== Successor '''delete''' ===Функция <texcode>\mathrm {successor '''func''' delete(Set<T> s, T elem)}: '''int''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green> '''while''' i < s.n '''and''' s.elements[i] != elem <font color=green>// Ищем индекс элемента ''elem''.</texfont color=green> i++ '''if''' i != s.n <font color=green> возвращает указатель на // Если элементнайден, стоящий после элемента то</font color=green> '''for''' j = i '''to''' s.n - 2 <font color=green>// сдвигаем все элементы массива, большие ''elem'',</font color=green> s.elements[j] = s.elements[j + 1] <texfont color=green>// на одну позицию влево (elemудаляется).</texfont color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green></code> множества Время выполнения {{---}} <tex>SetO(n)</tex>.

==Пример упорядоченного множества:= '''search''' === Примерами упорядоченных множеств могут служить такие структуры как деревьяДля нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].

<code> '''bool''' search(Set<T> s, T elem): '''int''' i = binSearch(s.elements, elem) '''return''' s.elements[i] == elem <font color=green>// Сравниваем найденное значение с искомым...</font color=green></code>Время выполнения {{---}} <tex>O(\log n)</tex>. === '''minimum''' ===Первый элемент множества минимальный, так как массив отсортирован по возрастанию. <code> '''T''' minimum(Set<T> s): '''T''' min = s.elements[0] '''return''' min</code>Время выполнения {{---}} <tex>O(1)</tex>. === '''maximum''' ===Выполняется аналогично операции <tex>\mathrm {minimum(set)}</tex>. <code> '''T''' maximum(Set<T> s): '''T''' max = s.elements[s.n - 1] '''return''' max</code>Время выполнения {{---}} <tex>O(1)</tex>. ==='''successor''' = Литература ==В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>. <code> '''T''' successor(Set<T> s, T elem): '''if''' elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального,</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green> '''else if''' elem < s.elements[0] '''return''' min(s) <font color=green>// Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// Иначе ищем элемент, больший ''elem''.</font color=green> '''return''' s.elements[i]</code>Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.  == Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']]. == Примеры == * Пустое множество <tex> \varnothing </tex>,* множество натуральных чисел <tex> \mathbb N </tex>,* множество целых чисел <tex> \mathbb Z </tex>,* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке]]. == Источники информации ==* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5* Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.* Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.* [http://ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество] [[Категория: Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория: Структуры данных]]