3622
правки
Изменения
Нет описания правки
Таким образом элементы с начала хранятся в левой ветке дерева, а с конца - в правой.
Наша структура данных персистентна, следовательно операция <tex> D.push\_front(x, ~D) </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex> , добавленным в началеначало <tex> D </tex>.
<code>
push_front(x, D) if D == <tex> \emptyset </tex> // если дек пустой, то формируем новый дек return Deque(x, <tex> \emptyset ,~ \varnothing </tex>) else if D.left == <tex> \varnothing </tex> // если левый ребенок не существует, то сделаем его новым элементом<tex> x </tex> левым ребёнком return Deque(x, D.child, D.right)
else
// иначе объединим его левого ребёнка с новым элементов элементом и попытаемся добавить в дек на следующем уровне return Deque(<tex> \varnothing </tex>, child.push_front(Pair(x, D.left), D.child), D.right)
</code>
Метод <tex> D.pop\_front(D) </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
<code>
pop_front(D) if D == <tex> \emptyset </tex> // изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек" return <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex> else if D.left <tex> \neq ~\varnothing</tex>
// если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка
return <tex> \mathcal{h} </tex>D.left, Deque(<tex> \varnothing </tex>, D.child, D.right)<tex> \mathcal{i} </tex> else if D.child == <tex> \varnothing</tex>
// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
// то вернём пару из правого ребёнка и абсолютно пустого дека
return <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
else
/*
* если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод pop_front()
* и возвращённую пару "элемент{{---}} новый дек" сохраняем в переменные temp & newDeque
* Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим
* или в деке будет отсутствовать ссылка на следующий дек
*/
temp, newDeque <tex> \leftarrow </tex> child.pop_front(D.child)
if temp == <tex> \varnothing </tex>
/*
* поэтому возвращаем right текущего дека и пустой дек
*/
return <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
else
/*
* нового дека, а right текущего right'ом нового
*/
return <tex> \mathcal{h} </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \mathcal{i} </tex>
</code>
Операции добавления в правый конец и извлечение из него делаются симметрично.
Таким образом, если мы добавляем элементы только в один конец, то на <tex> i </tex>-ом уровне дека не более <tex> 2^i </tex> элементов. Пусть глубина текущего дека <tex> d. </tex> Тогда в нём может находится не более <tex> n ~=~ 1 ~+~ 2 ~+~ 4 ~+...+~ 2^d </tex> объектов, откуда получаем <tex> d = \mathcal{b} \log_2 ~n \mathcal{c} </tex>.
Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> O(\log ~n) </tex>
== Описание асипмтотики Пример ==
Рассмотрим поподробнее асимптотику операцийоперации. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.
=== push_front ===
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Этот элемент встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Добавим третий элемент. После предыдущего действия появилась свободная вакансия на место левого ребёнка дека первого уровня, поэтому новый элемент занимает это место. И, наконец, добавим 4-ый элемент. Он объединяется в пару с левым ребёнком дека первого уровня, затем новая пара объединяется со старой парой на втором уровне и добавляется в дек на высоте 2. И так далее.
[[Файл:PushDequeExample.png]]
=== pop_front ===
