Implement an immutable deque as a balanced binary

I've been thinking for a while about how to go about implementing a deque (that is, a double-ended queue) as an immutable data structure.

There seem to be different ways of doing this. AFAIK, immutable data structures are generally hierarchical, so that major parts of it can be reused after modifying operations such as the insertion or removal of an item.

Eric Lippert has two articles on his blog about this topic, along with sample implementations in C#.

Both of his implementations strike me as more elaborate than is actually necessary. Couldn't deques simply be implemented as binary trees, where elements can only be inserted or removed on the very "left" (the front) and on the very "right" (the back) of the tree?

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

Additionally, the tree would be kept reasonably balanced with rotations:

right rotations upon insertion at the front or upon removal from the back, and
left rotations upon removal from the front or insertion at the back.

Eric Lippert is, in my opinion, a very smart person whom I deeply respect, yet he apparently didn't consider this approach. Thus I wonder, was it for a good reason? Is my suggested way of implementing deques naïve?

回答1:

As Daniel noted, implementing immutable deques with well-known balanced search trees like AVL or red-black trees gives Θ(lg n) worst case complexity. Some of the implementations Lippert discusses may seem elaborate at first glance, but there are many immutable deques with o(lg n) worst or average or amortized complexity that are built from balanced trees along with two simple ideas:

Reverse the Spines

To perform deque operations on a traditional balanced search tree, we need access to the ends, but we only have access to the center. To get to the left end, we must navigate left child pointers until we finally reach a dead end. It would be preferable to have a pointer to the left and right ends without all that navigation effort. In fact, we really don't need access to the root node very often. Let's store a balanced search tree so that access to the ends is O(1).

Here is an example in C of how you might normally store an AVL tree:
```
struct AVLTree {
  const char * value;
  int height;
  struct AVLTree * leftChild;
  struct AVLTree * rightChild;
};
```
To set up the tree so that we can start at the edges and move towards the root, we change the tree and store all of the pointers along the paths from the root to the left and rightmost children in reverse. (These paths are called the left and right spine, respectively). Just like reversing a singly-linked list, the last element becomes the first, so the leftmost child is now easily accessible.

This is a little tricky to understand. To help explain it, imagine that you only did this for the left spine:
```
struct LeftSpine {
  const char * value;
  int height;
  struct AVLTree * rightChild;
  struct LeftSpine * parent;
};
```
In some sense, the leftmost child is now the "root" of the tree. If you drew the tree this way, it would look very strange, but if you simply take your normal drawing of a tree and reverse all of the arrows on the left spine, the meaning of the LeftSpine struct should become clearer. Access to the left side of the tree is now immediate. The same can be done for the right spine:
```
struct RightSpine {
  double value;
  int height;
  struct AVLTree * leftChild;
  struct RightSpine * parent;
};
```
If you store both a left and a right spine as well as the center element, you have immediate access to both ends. Inserting and deleting may still be Ω(lg n), because rebalancing operations may require traversing the entire left or right spine, but simply viewing to the left and rightmost elements is now O(1).

An example of this strategy is used to make purely functional treaps with implementations in SML and Java (more documentation). This is also a key idea in several other immutable deques with o(lg n) performance.
Bound the Rabalancing Work

As noted above, inserting at the left or rightmost end of an AVL tree can require Ω(lg n) time for traversing the spine. Here is an example of an AVL tree that demonstrates this:

A full binary tree is defined by induction as:
- A full binary tree of height 0 is an empty node.
- A full binary tree of height n+1 has a root node with full binary trees of height n as children.
Pushing an element onto the left of a full binary tree will necessarily increase the maximum height of the tree. Since the AVL trees above store that information in each node, and since every tree along the left spine of a full binary tree is also a full binary tree, pushing an element onto the left of an AVL deque that happens to be a full binary tree will require incrementing Ω(lg n) height values along the left spine.

(Two notes on this: (a) You can store AVL trees without keeping the height in the node; instead you keep only balance information (left-taller, right-taller, or even). This doesn't change the performance of the above example. (b) In AVL trees, you might need to do not only Ω(lg n) balance or height information updates, but Ω(lg n) rebalancing operations. I don't recall the details of this, and it may be only on deletions, rather than insertions.)

In order to achieve o(lg n) deque operations, we need to limit this work. Immutable deques represented by balanced trees usually use at least one of the following strategies:
- Anticipate where rebalancing will be needed. If you are using a tree that requires o(lg n) rebalancing but you know where that rebalancing will be needed and you can get there quickly enough, you can perform your deque operations in o(lg n) time. Deques that use this as a strategy will store not just two pointers into the deque (the ends of the left and right spines, as discussed above), but some small number of jump pointers to places higher along the spines. Deque operations can then access the roots of the trees pointed to by the jump pointers in O(1) time. If o(lg n) jump pointers are maintained for all of the places where rebalancing (or changing node information) will be needed, deque operations can take o(lg n) time.
  
  (Of course, this makes the tree actually a dag, since the trees on the spines pointed to by jump pointers are also pointed to by their children on the spine. Immutable data structures don't usually get along with non-tree graphs, since replacing a node pointed to by more than one other node requires replacing all of the other nodes that point to it. I have seen this fixed by just eliminating the non-jump pointers, turning the dag back into a tree. One can then store a singly-linked list with jump pointers as a list of lists. Each subordinate list contains all of the nodes between the head of that list and its jump pointer. This requires some care to deal with partially overlapping jump pointers, and a full explanation is probably not appropriate for this aside.)
  
  This is one of the tricks used by Tsakalidis in his paper "AVL Trees for localized search" to allow O(1) deque operations on AVL trees with a relaxed balance condition. It is also the main idea used by Kaplan and Tarjan in their paper "Purely functional, real-time deques with catenation" and a later refinement of that by Mihaesau and Tarjan. Munro et al.'s "Deterministic Skip Lists" also deserves a mention here, though translating skip lists to an immutable setting by using trees sometimes changes the properties that allow such efficient modification near the ends. For examples of the translation, see Messeguer's "Skip trees, an alternative data structure to Skip lists in a concurrent approach", Dean and Jones's "Exploring the duality between skip lists and binary search trees", and Lamoureux and Nickerson's "On the Equivalence of B-trees and deterministic skip lists".
- Do the work in bulk. In the full binary tree example above, no rebalancing is needed on a push, but Ω(lg n) nodes need to have their height or balance information updated. Instead of actually doing the incrementation, you could simply mark the spine at the ends as needing incrementation.
  
  One way to understand this process is by analogy to binary numbers. (2^n)-1 is represented in binary by a string of n 1's. When adding 1 to this number, you need to change all of the 1's to 0's and then add a 1 at the end. The following Haskell encodes binary numbers as non-empty strings of bits, least significant first.
```
data Bit = Zero | One

type Binary = (Bit,[Bit])

incr :: Binary -> Binary
incr (Zero,x) = (One,x)
incr (One,[]) = (Zero,[One])
incr (One,(x:xs)) = 
    let (y,ys) = incr (x,xs)
    in (Zero,y:ys)
```
  incr is a recursive function, and for numbers of the form (One,replicate k One), incr calls itself Ω(k) times.
  
  Instead, we might represent groups of equal bits by only the number of bits in the group. Neighboring bits or groups of bits are combined into one group if they are equal (in value, not in number). We can increment in O(1) time:
```
data Bits = Zeros Int | Ones Int

type SegmentedBinary = (Bits,[Bits])

segIncr :: SegmentedBinary -> SegmentedBinary
segIncr (Zeros 1,[]) = (Ones 1,[])
segIncr (Zeros 1,(Ones n:rest)) = (Ones (n+1),rest)
segIncr (Zeros n,rest) = (Ones 1,Zeros (n-1):rest)
segIncr (Ones n,[]) = (Zeros n,[Ones 1])
segIncr (Ones n,(Zeros 1:Ones m:rest)) = (Zeros n,Ones (m+1):rest)
segIncr (Ones n,(Zeros p:rest)) = (Zeros n,Ones 1:Zeros (p-1):rest)
```
  Since segIncr is not recursive and doesn't call any functions other than plus and minus on Ints, you can see it takes O(1) time.
  
  Some of the deques mentioned in the section above entitled "Anticipate where rebalancing will be needed" actually use a different numerically-inspired technique called "redundant number systems" to limit the rebalancing work to O(1) and locate it quickly. Redundant numerical representations are fascinating, but possibly too far afield for this discussion. Elmasry et al.'s "Strictly-regular number system and data structures" is not a bad place to start reading about that topic. Hinze's "Bootstrapping one-sided flexible arrays" may also be useful.
  
  In "Making data structures persistent", Driscoll et al. describe lazy recoloring, which they attribute to Tsakalidis. They apply it to red-black trees, which can be rebalanced after insertion or deletion with O(1) rotations (but Ω(lg n) recolorings) (see Tarjan's "Updataing a balanced tree in O(1) rotations"). The core of the idea is to mark a large path of nodes that need to be recolored but not rotated. A similar idea is used on AVL trees in the older versions of Brown & Tarjan's "A fast merging algorithm". (Newer versions of the same work use 2-3 trees; I have not read the newer ones and I do not know if they use any techniques like lazy recoloring.)
- Randomize. Treaps, mentioned above, can be implemented in a functional setting so that they perform deque operations on O(1) time on average. Since deques do not need to inspect their elements, this average is not susceptible to malicious input degrading performance, unlike simple (no rebalancing) binary search trees, which are fast on average input. Treaps use an independent source of random bits instead of relying on randomness from the data.
  
  In a persistent setting, treaps may be susceptible to degraded performance from malicious input with an adversary who can both (a) use old versions of a data structure and (b) measure the performance of operations. Because they do not have any worst-case balance guarantees, treaps can become quite unbalanced, though this should happen rarely. If an adversary waits for a deque operation that takes a long time, she can initiate that same operation repeatedly in order to measure and take advantage of a possibly unbalanced tree.
  
  If this is not a concern, treaps are an attractively simple data structure. They are very close to the AVL spine tree described above.
  
  Skip lists, mentioned above, might also be amenable to functional implementations with O(1) average-time deque operations.
  
  The first two techniques for bounding the rebalancing work require complex modifications to data structures while usually affording a simple analysis of the complexity of deque operations. Randomization, along with the next technique, have simpler data structures but more complex analysis. The original analysis by Seidel and Aragon is not trivial, and there is some complex analysis of exact probabilities using more advanced mathematics than is present in the papers cited above -- see Flajolet et al.'s "Patterns in random binary search trees".
- Amortize. There are several balanced trees that, when viewed from the roots up (as explained in "Reverse the Spines", above), offer O(1) amortized insertion and deletion time. Individual operations can take Ω(lg n) time, but they put the tree in such a nice state that a large number of operations following the expensive operation will be cheap.
  
  Unfortunately, this kind of analysis does not work when old versions of the tree are still around. A user can perform operations on the old, nearly-out-of-balance tree many times without any intervening cheap operations.
  
  One way to get amortized bounds in a persistent setting was invented by Chris Okasaki. It is not simple to explain how the amortization survives the ability to use arbitrary old versions of a data structure, but if I remember correctly, Okasaki's first (as far as I know) paper on the subject has a pretty clear explanation. For more comprehensive explanations, see his thesis or his book.
  
  As I understand it, there are two essential ingredients. First, instead of just guaranteeing that a certain number of cheap operations occur before each expensive operation (the usual approach to amortization) you actually designate and set up that specific expensive operation before performing the cheap operations that will pay for it. In some cases, the operation is scheduled to be started (and finished) only after many intervening cheap steps. In other cases, the operation is actually scheduled only O(1) steps in the future, but cheap operations may do part of the expensive operation and then reschedule more of it for later. If an adversary looking to repeat an expensive operation over and over again is actually reusing the same scheduled operation each time. This sharing is where the second ingredient comes in.
  
  The computation is set up using laziness. A lazy value is not computed immediately, but, once performed, its result is saved. The first time a client needs to inspect a lazy value, its value is computed. Later clients can use that cached value directly, without having to recompute it.
```
#include <stdlib.h>

struct lazy {
  int (*oper)(const char *);
  char * arg;
  int* ans;
};

typedef struct lazy * lazyop;

lazyop suspend(int (*oper)(const char *), char * arg) {
  lazyop ans = (lazyop)malloc(sizeof(struct lazy));
  ans->oper = oper;
  ans->arg = arg;
  return ans;
}

void force(lazyop susp) {
  if (0 == susp) return;
  if (0 != susp->ans) return;
  susp->ans = (int*)malloc(sizeof(int));
  *susp->ans = susp->oper(susp->arg);
}

int get(lazyop susp) {
  force(susp);
  return *susp->ans;
}
```
  Laziness constructs are included in some MLs, and Haskell is lazy by default. Under the hood, laziness is a mutation, which leads some authors to call it a "side effect". That might be considered bad if that kind of side effect doesn't play well with whatever the reasons were for selecting an immutable data structure in the first place, but, on the other hand, thinking of laziness as a side effect allows the application of traditional amortized analysis techniques to persistent data structures, as mentioned in a paper by Kaplan, Okasaki, and Tarjan entitled "Simple Confluently Persistent Catenable Lists".
  
  Consider again the adversary from above who is attempting to repeatedly force the computation of an expensive operation. After the first force of the lazy value, every remaining force is cheap.
  
  In his book, Okasaki explains how to build deques with O(1) amortized time required for each operation. It is essentially a B+-tree, which is a tree where all of the elements are stored at the leaves, nodes may vary in how many children they have, and every leaf is at the same depth. Okasaki uses the spine-reversal method discussed above, and he suspends (that is, stores as a lazy value) the spines above the leaf elements.
  
  A structure by Hinze and Paterson called "Finger trees: a simple general-purpose data structure" is halfway between the deques designed by Okasaki and the "Purely functional representations of catenable sorted lists" of Kaplan and Tarjan. Hinze and Paterson's structure has become very popular.
  
  As a evidence of how tricky the amortized analysis is to understand, Hinze and Paterson's finger trees are frequently implemented without laziness, making the time bounds not O(1) but still O(lg n). One implementation that seems to use laziness is the one in functional-dotnet. That project also includes an implementation of lazy values in C# which might help explain them if my explanation above is lacking.

Could deques be implemented as binary trees? Yes, and their worst-case complexity when used persistently would be no worse than those presented by Eric Lippert. However, Eric's trees are actually not complicated enough to get O(1) deque operations in a persistent setting, though only by a small complexity margin (making the center lazy) if you are willing to accept amortized performance. A different but also simple view of treaps can get O(1) expected performance in a functional setting, assuming an adversary who is not too tricky. Getting O(1) worst-case deque operations with a tree-like structure in a functional setting requires a good bit more complexity than Eric's implementations.

Two final notes (though this is a very interesting topic and I reserve the right to add more later) :-)

Nearly all of the deques mentioned above are finger search trees as well. In a functional setting this means they can be split at the ith element in O(lg(min(i,n-i))) time and two trees of size n and m can be concatenated in O(lg(min(n,m))) time.
I know of two ways of implementing deques that don't use trees. Okasaki presents one in his book and thesis and the paper I linked to above. The other uses a technique called "global rebuilding" and is presented in Chuang and Goldberg's "Real-time deques, multihead Turing machines, and purely functional programming".

回答2:

The other answers are all awesome. I will add to them that I chose the finger tree implementation of a deque because it makes an unusual and interesting use of the generic type system. Most data structures are recursive in their structure, but this technique puts the recursion also in the type system which I had not seen before; I thought it might be of general interest.

回答3:

If you use a balanced binary tree, insertions and removals on both ends are O(lg N) (both average and worst case). The approach used in Eric Lippert's implementations is more efficient, running in constant time in the average case (the worst case still is O(lg N)).

Remember that modifying an immutable tree involves rewriting all parents of the node you are modifying. So for a deque, you do not want the tree to be balanced; instead you want the L and R nodes to be as close to the root as possible, whereas nodes in the middle of the tree can be further away.

回答4:

Couldn't deques simply be implemented as binary trees, where elements can only be inserted or removed on the very "left" (the front) and on the very "right" (the back) of the tree?

Absolutely. A modified version of a height-balanced tree, AVL trees in particular, would be very easy to implement. However it means filling tree-based queue with n elements requires O(n lg n) time -- you should shoot for a deque which has similar performance characteristics as the mutable counterpart.

You can create a straightforward immutable deque with amortized constant time operations for all major operations using two stacks, a left and right stack. PushLeft and PushRight correspond to pushing values on the left and right stack respectively. You can get Deque.Hd and Deque.Tl from the LeftStack.Hd and LeftStack.Tl; if your LeftStack is empty, set LeftStack = RightStack.Reverse and RightStack = empty stack.

type 'a deque = Node of 'a list * 'a list    // '

let peekFront = function
    | Node([], []) -> failwith "Empty queue"
    | Node(x::xs, ys) -> x
    | Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
    | Node([], []) -> failwith "Empty queue"
    | Node(xs, y::ys) -> y
    | Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
    | Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
    | Node(xs, ys) -> Node(xs, v::ys)
let tl = function
    | Node([], []) -> failwith "Empty queue"
    | Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
    | Node(x::xs, ys) -> Node(xs, ys)

This is a very common implementation, and its very easy to optimize for better performance.