Изменения
→successor
* <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>settrue</tex> при наличии элемента в множестве или специальное значение <tex>nullfalse</tex>, если такого элемента нетв противном случае,
* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
== Наивная реализация на массиве ==
Упорядоченное множество <tex>sets</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
<code>
'''func''' insert(Set<T> s, T elem):
s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green>
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
'''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>
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>
'''Tbool''' search(Set<T> s, T elem): '''if''' s.elements[0] <= elem '''&&''' s.elements[s.n] >= elem <font color=green>// Если элемент ''elem'' существует, то</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// ищем индекс элемента ''elem''</font color=green> '''return''' s.elements[i] == elem <font color=green>// и выводим его Сравниваем найденное значениес искомым..</font color=green> '''else''' <font color=green>// В противном случае</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green>
</code>
Время выполнения {{---}} <tex>O(\log\ n)</tex>.
=== '''minimum''' ===
<code>
'''T''' maximum(Set<T> s):
'''T''' max = s.elements[0s.n - 1]
'''return''' max
</code>
Время выполнения {{---}} <tex>O(1)</tex>.
=== '''successor''' ===
<code>
'''T''' successor(Set<T> s, T elem):
'''if''' s.elements[0] <= elem '''&&''' > s.elements[s.n- 1] > elem <font color=green>// Если элемент ''elem'' существует и не равен максимальномубольше максимального,</font color=green> '''intreturn''' ''null'' i = binSearch(s.elements, elem) <font color=green>// то ищем индекс элемента возвращаем ''elemnull''.</font color=green> '''returnelse if''' elem < s.elements[i + 10] '''return''' min(s) <font color=green>// и выводим следующий за ним Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''elseint''' i = binSearch(s.elements, elem) <font color=green>// В противном случаеИначе ищем элемент, больший ''elem''.</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''s.</font color=green>elements[i]
</code>
Время выполнения {{---}} <tex>O(\log\ n)</tex>.Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==
* множество натуральных чисел <tex> \mathbb N </tex>,
* множество целых чисел <tex> \mathbb Z </tex>,
* строки, отсортированные в лексикографическом порядке. == См. также ==* [[Бинарный поисклексикографический порядок|Вещественный двоичный поисклексикографическом порядке]].
== Источники информации ==
