Изменения

Чтобы работать со множеством было проще - используют '''упорядоченное Упорядоченное множество''', где можно совершать следующие операции: <tex>Search(x)</tex> (поиск), <tex>Minimum</tex> (минимумангл. ''ordered set'')представляет собой коллекцию элементов, <tex>Maximum</tex> (максимум), <tex>Predecessor</tex> (предыдущий), <tex>Successor</tex> (следующий), <tex>Insert(x)</tex> (вставить), и <tex>Delete(x)</tex> (удалить).== Search ==Процедура поиска получает на вход искомый каждому из которых присваивается определенный ключ <tex>x</tex>, и возвращает указатель на элемент множества или специальное значение <tex>NIL</tex>, если такого отвечающий за порядок этого элемента нет.== Minimum ==Процедура <tex>Minimum</tex> возвращает указатель на минимальный элемент множества.== Maximum ==Процедура <tex>Maximum</tex> возвращает указатель на максимальный элемент множества.== Predecessor ==Процедура <tex>Predecessor</tex> возвращает указатель на предыдущий элемент множествав множестве.== Successor ==Процедура <tex>Successor</tex> возвращает указатель Бинарное отношение на следующий элемент множества.== Insert ==Процедура <tex>Insert(x)</tex> добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности).== Delete ==Параметром процедуры <tex>Delete(x)</tex> удаления упорядоченном множестве является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности)[[отношение порядка|отношением порядка]].

'''Вполне упорядоченным множеством''', которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент. == Операции над упорядоченным множеством ==Над упорядоченным множеством <tex>set</tex> заданы следующие операции:* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),* <tex>\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>set</tex>.* <tex>\mathrm {successor(set, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>. == Наивная реализация на массиве ==Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>. Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива. <code> '''struct''' Set<T>: '''int''' n <font color=green>// количество элементов множества</font color=green> '''T'''[n] elements <font color=green>// массив элементов множества типа ''T''</font color=green></code> === '''insert''' ===<code> '''func''' insert(Set<T> s, T elem): s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font 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>O(n)</tex>. === '''delete''' ===<code> '''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''.</font 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] <font color=green>// на одну позицию влево (elem удаляется).</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green></code>Время выполнения {{---}} <tex>O(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/Упорядоченное_множество Википедия — Упорядоченное множество] [[Категория: Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория: Структуры данных]]