Изменения

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

==Операции над упорядоченным множеством==Над упорядоченным множеством <tex>Setset</tex> заданы следующие операции:=== Insert ===Функция * <tex>\mathrm {insert(Setset, elem, elemKey)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex>в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности), имеющий ключ * <tex>elemKey\mathrm {delete(set, elem)}</tex>{{---}} удаляет элемент <tex>elem</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>Setset</tex> .* <tex>\mathrm {successor(сохраняя свойство упорядоченностиset, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>.

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

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

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

=== Maximum '''insert''' ===Функция <texcode>\mathrm {maximum '''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]) <font color=green>// пока ''elem'' не окажется в нужном месте.</font color=green></code>Время выполнения {{---}} <tex>SetO(n)</tex>.

=== Predecessor '''delete''' ===Функция <texcode>\mathrm {predecessor '''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> возвращает указатель на // Если элементнайден, стоящий перед элементом то<tex/font color=green> '''for''' j = i '''to''' s.n - 2 <font color=green>// сдвигаем все элементы массива, большие ''elem'',</font color=green> s.elements[j] = s.elements[j + 1] <font color=green>// на одну позицию влево (elemудаляется).</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</texfont color=green></code> множества Время выполнения {{---}} <tex>SetO(n)</tex>.

=== Successor '''search''' ===Функция <tex>\mathrm {successor(Set, elem)}</tex> возвращает указатель на элемент, стоящий после элемента <tex>elem</tex> множества <tex>Set</tex>Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].

<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/Упорядоченное_множество Википедия — Упорядоченное множество] [[Категория: Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория: Структуры данных]]