1632
правки
Изменения
м
=== '''predecessor''' ===
Выполняется аналогично операции <tex>\mathrm {search(set, elem)}</tex>.
<code>
'''T''' predecessor(Set<T> s, T elem):
'''int''' i = binSearch(s.elements, elem)
'''if''' s.elements[i] == elem '''and''' i > 0 <font color=green>// Элемент, предшествующий первому, не существует.</font color=green>
'''return''' s.elements[i - 1]
'''else'''
'''return''' ''null''
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
'''int''' i
rollbackEdits.php mass rollback
</code>
Время выполнения {{---}} <tex>O(1)</tex>.
=== '''successor''' ===
В операции используется [[Целочисленный двоичный поиск|левосторонний правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]<elem\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>
'''elseif'''elem < s.elements[0] '''ifreturn''' elem < min(s.elements[0] ) <font color=green>// Если элемент меньше минимального,</font color=green> i = 0 <font color=green>// возвращаем минимальный элемент.</font color=green> '''elseint''' i = binSearch(s.elements, elem) <font color=green>// Иначе ищем элемент, больший либо равный ''elem''.</font color=green> '''if''' s.elements[i] == elem '''return''' s.elements[i + 1] '''else''' '''return''' s.elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==
