3622
правки
Изменения
→Эффективная реализация
== Эффективная реализация ==
=== Способ хранения структуры ===
[[Файл:Tree_deque.png|220px|right]]
Персистентный дек можно визуально представить как [[Список#Односвязный список | односвязный список]], где каждый узел хранит пару {{---}} левый элемент и правый, а также ''ребёнка'' {{---}} ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа ''пара''.
Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>\mathrm{first}</tex> и <tex>\mathrm{last}</tex> типов <tex>T</tex>.
<code style = "display: inline-block;">
'''class''' Pair<T>:
Наша структура данных персистентна, следовательно операция <tex> \mathrm{pushFront(x, ~D)} </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.
=== push ===Пустой дек будем обозначать значком <tex> \emptyset </tex>, а пустую пару {{---}} <tex> \varnothing </tex>, чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю <tex>\mathrm{left}</tex>. Если же работаем с концом, то обращаемся сперва к полю <tex>\mathrm{right}</tex>.
<code>
'''Deque<T>''' pushFront(x: '''T''', D: '''Deque<T>'''):
</code>
=== pop ===
Метод <tex> \mathrm{popFront(D)} </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
<code>
* или в деке будет отсутствовать ссылка на следующий дек.
*/</font>
(temp, newDeque <tex> \leftarrow </tex> ) = popFront(D.child)
<font color=darkgreen>/*
* здесь <tex>temp</tex> всегда не пуст; надо вернуть первый элемент пары temp
Операции добавления в правый конец и извлечение из него делаются симметрично.
=== Асимптотика времени работы ===Таким образом, если мы добавляем элементы только в один конец, то на <tex> i </tex>-ом уровне дека не более <tex> 2^i </tex> элементов. Пусть глубина текущего дека <tex> d. </tex> Тогда в нём может находится не более <tex> n = 1 + 2 + 4 +...\ldots + 2^d </tex> объектов, откуда получаем <tex> d = \mathcal{b} \log_2 n \mathcal{c} </tex>.
Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> \mathcal{O}(\log n) </tex>
== Пример ==
