3622
правки
Изменения
→Эффективная реализация
[[Файл:Tree_deque.png|220px|right]]
Персистентный дек можно визуально представить как [[Список#Односвязный список | односвязный список]], где каждый узел хранит пару {{--- }} левый элемент и правый, а также ''ребёнка'' {{---}} ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа ''пара''.
Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T</tex>.
<code style = "display: inline-block;">
'''class''' Pair<T> {:
T first
T last
</code>
Сам дек можно инициализировать напрямую, вызвав конструктор <tex>\mathrm{Deque(left, ~child, ~right)}</tex>, или . Описание структуры через шаблоны шаблон <tex>\mathrm{Deque{<}T{>}}</tex>, тогда произойдёт следующее:
<code style = "display: inline-block;">
'''class''' Deque<T> {:
T left
T right
Deque<Pair<T>> child
</code>
Наша структура данных персистентна, следовательно операция <tex> \mathrm{pushFront(x, ~D)} </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.
Пустой дек будем обозначать значком <tex> \emptyset </tex>, а пустую пару {{---}} <tex> \varnothing </tex>, чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю <tex>left</tex>. Если же работаем с концом, то обращаемся сперва к полю <tex>right</tex>.
<code>
'''pushFrontDeque<T>'''pushFront(x: '''T''', D: '''Deque<T>'''):
'''if''' D == <tex> \emptyset </tex>
<font color=darkgreen>// если дек пустой, то формируем новый дек</font>
'''return''' Deque(x, <tex> \emptyset ,~ \varnothing </tex>)
'''else if''' D.left == <tex> \varnothing </tex>
<font color=darkgreen>// если левый ребенок не существует, то сделаем <tex> x </tex> левым ребёнком</font>
'''return''' Deque(x, D.child, D.right)
'''else'''
<font color=darkgreen>// иначе объединим левого ребёнка с новым элементом и попытаемся добавить в дек на следующем уровне</font>
'''return''' Deque(<tex> \varnothing </tex>, pushFront(Pair(x, D.left), D.child), D.right)
</code>
Метод <tex> \mathrm{popFront(D)} </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
<code>
'''popFrontPair<T, Deque<T>>'''popFront(D: '''Deque<T>'''):
'''if''' D == <tex> \emptyset </tex>
<font color=darkgreen>// изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"</font>
'''return''' <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex>
'''elseif''' if D.left <tex> \neq ~\varnothing</tex> <font color=darkgreen>// если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка, // но если остался только левый ребёнок, но возвращаем его и пустой дек</font>
'''if''' D.child == <tex> \emptyset </tex> '''and''' D.right == <tex> \varnothing </tex>
'''return''' <tex> \mathcal{h} </tex>D.left, <tex> \emptyset \mathcal{i} </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>
<font color=darkgreen>// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует, // то вернём пару из правого ребёнка и абсолютно пустого дека</font>
'''return''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
'''else'''
<font color=darkgreen>/*
* если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex>\mathrm{popFront}</tex>
* и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <tex>temp</tex> и <tex>newDeque</tex>.
* Рекурсивные вызовы прекратятся, как только левый ребёнок окажется не пустым
* или в деке будет отсутствовать ссылка на следующий дек.
*/ </font>
temp, newDeque <tex> \leftarrow </tex> popFront(D.child)
'''if''' temp == <tex> \varnothing </tex>
<font color=darkgreen>/*
* это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты,
* значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и <tex>child</tex> ссылается на абсолютно пустой дек,
* поэтому возвращаем <tex>right</tex> текущего дека и пустой дек
*/</font>
'''return''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
'''else'''
<font color=darkgreen>/*
* если всё же <tex>temp</tex> не пуст, то надо вернуть первый элемент пары temp;
* в качестве left нового дека надо поставить <tex>temp.last</tex> (на уровне ниже <tex>temp</tex> хранил
* требуемому количеству элементов); <tex>newDeque</tex> делаем <tex>child</tex>'ом
* нового дека, а <tex>right</tex> текущего <tex>right</tex>'ом нового
*/</font>
'''return''' <tex> \langle </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \rangle </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>
== Пример ==
