3622
правки
Изменения
Нет описания правки
== Эффективная реализация ==
[[Файл:Tree_deque.png|thumb|220px|right|Древовидная структура дека]]
Персистентный дек можно визуально представить как деревоодносвязный список, где каждый узел хранит пару - левый элемент и правый, а также ''ребёнка'' {{- --}} ссылку на следующий декузел. Только с каждым уровнем вложенности левый и правый элемент каждого узла хранят в два раза больше объектов, чем на предыдущем уровнепредыдущий. Это удобно сделать с помощью типа ''пара''.
Тип <tex>Pair</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T</tex>.
};
</code>
<code>
push_front(x, D)
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление 1 к разряду числа в двоичном представлении: если в разряде 1, то подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.
[[Файл:PushDequeExample.png|700px]]
=== pop_front ===
Запустим первый <tex> pop\_front() </tex>. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару <tex> \left \langle temp, ~newDeque \right \rangle </tex> сохранятся две пары элементов и пустой дек высоты 0. Так как <tex> temp </tex> не пуст, то в предыдущий рекурсивный вызов вернётся пара: в temp новый сохранится пара ''4 3'', на текущем уровне будет пара ''2 1'', а <tex> child </tex> будет ссылаться на пустой дек. Потом пара ''4 3'' передастся выше, ''child'' сохраняет ссылку на предыдущий дек, и, наконец, ''4'' извлечётся. И так далее. Аналогично добавлению, процесс извлечения элемента можно представить, как вычитание 1 из младшего разряда двоичного числа.
[[Файл:PopDequeExample.png|700px]]
== См. также ==
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Персистентный стек]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
/tex>, push_front(Pair(x, D.left), D.child), D.right)
