Изменения

Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Этот элемент Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Добавим третий элемент. После предыдущего действия появилась свободная вакансия на место левого ребёнка дека первого уровняПроцесс добавления можно представить, поэтому новый элемент занимает это место. Икак прибавление 1 к разряду числа в двоичном представлении: если в разряде 1, наконец, добавим 4то подряд идущие за ней единицы обнулятся {{---ый элемент. Он объединяется }} элементы объединяются в пару с левым ребёнком дека первого уровняпары, затем новая пара объединяется со старой парой иначе становятся на втором уровне и добавляется в дек на высоте 2. И так далееместо этого разряда.

Запустим первый <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'' извлечётся. И так далее. Как видноАналогично добавлению, <tex> pop </tex> тоже выполняется за <tex> O(\log ~ n)процесс извлечения элемента можно представить, как вычитание 1 из младшего разряда двоичного числа. </tex>