Implement an immutable deque as a balanced binary tree?

Question

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?

Answer 1

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.

Answer 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.

Answer 3

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.