Изменения

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

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

=== Search =Операции над упорядоченным множеством ==Процедура поиска Над упорядоченным множеством <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>xelem</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>NILset</tex>.* <tex>\mathrm {successor(set, elem)}</tex>{{---}} возвращает элемент, если такого стоящий после элемента нет<tex>elem</tex> множества <tex>set</tex>.

=== Minimum =Наивная реализация на массиве ==Процедура Упорядоченное множество <tex>s</tex>, содержащее <tex>Minimumn</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex> возвращает указатель на минимальный элемент множества.

=== Maximum ===Процедура <tex>Maximum</tex> возвращает указатель Рассмотрим реализацию на максимальный элемент множествапримере отсортированного по возрастанию целочисленного массива.

<code> '''struct''' Set<T>: '''int''' n <font color=green>// количество элементов множества</font color=green> '''T'''[n] elements <font color= Predecessor ==green>// массив элементов множества типа ''T''</font color=green>Процедура <tex>Predecessor</texcode> возвращает указатель на предыдущий элемент множества.

=== Successor '''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>SuccessorO(n)</tex> возвращает указатель на следующий элемент множества.

=== Insert '''delete''' ===Процедура <texcode> '''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>Insert// на одну позицию влево (xelem удаляется).</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green></code>Время выполнения {{---}} <tex> добавляет заданный элемент в подходящее место множества O(сохраняя свойство упорядоченностиn)</tex>.

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