*/</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 * (в этом блоке temp всегда будет иметь тип <tex>\mathrm{Pair}</tex>); * в качестве left нового дека надо поставить <tex>temp.last</tex> (на уровне ниже <tex>temp</tex> хранил * в два раза больше элементов, поэтому на текущем уровне <tex>temp.last</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>
