This is a simple immutable deque based on binary trees. What do you think about it? Does this kind of data structure, or possibly an improvement thereof, seem useful? How could I improve it, preferably without getting rid of its strengths? (Not in the sense of more operations, in the sense of different design) Does this sort of thing have a name?

Red nodes are newly instantiated; blue ones are reused. Nodes aren't actually red or anything, it's just for emphasis.


Note that right deques do not take O(n). Any access to an element in the deque depends on how long ago it was inserted. You can perform any enqueue or concat operation at O(1).

You can also use the 'weight' of each non-leaf node to change the orientation of the tree, such as to make all right access costly and left access cheap, or to provide O(logn) access to either end. This process takes O(n) worst case, depending on the initial orientation of the tree.

Alternatively, I could 'search' for the lightest node into which to insert a given node, turning all operations into O(logn) operations.


3 Answers 3


Congratulations you invented the immutable list. It appears in every functional language and is the bread and butter of functional programming. It's not often used as a dequeue though.

For that purpose there are better data-structures. I recommend reading "Purely Functional Data Structures" by Chris Okasaki if you'd like to gain some insight into the different data-structures that exist.

  • 1
    Thanks for the comment, but isn't the standard implementation of a single-directional immutable list basically a linked list that only supports cheap addition/deletion from one side\? This one supports expensive or cheap access depending on how recently an item was inserted, and enqueues are always cheap.
    – GregRos
    Commented Jul 2, 2012 at 9:46
  • @GregRos, I missed that slight variation, but wouldn't a immutable dequeue that supports O(1) enqueue and dequeue to both ends be more useful (of which there are implementations). Commented Jul 2, 2012 at 9:59
  • Ah, I'm fully aware it's a problematic implementation, I just wanted to know if/how it could be improved, and if this implementation has a name. Also, what are the other implementations of deques besides finger trees? (which I readily admit are far superior to this data structure in almost every way)
    – GregRos
    Commented Jul 2, 2012 at 10:58
  • 2
    @GregRos, see this stack overflow answer that sheds some light on purely functional queues with amortized and worst-case bounds. Commented Jul 2, 2012 at 11:22

You've rediscovered a couple of things...

  1. "Binary tree" does not automatically mean "binary search tree".

  2. The text-book form of a data structure isn't the end of the story. Data structures can be adapted and "augmented". Some augmented data structures are text-book examples in their own right - e.g. interval trees.

Adding extra summary data to each node is a fairly common trick with tree data structures. A favorite of mine is including subtree size information alongside key summaries. In that way, I have containers that can easily support subscripted access as well as key-based search. In my case, these are multiway trees with all data items in the leaf nodes (basically B+ trees). So the keys in the branch nodes are really just another form of summary - the first (or last) key in the subtree. With both subtree-sizes and discrete-typed keys, another sometimes-useful trick is being able to search in O(log n) time for the lowest key >= some minimum that isn't already present in the tree.

And obviously, it's just as valid to not have keys at all if you don't need them. A container that supports subscripting but not key-based search is, of course, an array or vector. A multiway tree version might be appropriate if you need a huge vector with frequent insertions/deletions at arbitrary positions, though it's a niche thing at best. A binary tree based vector might have some niche application too.

One example I have using subtree size summaries isn't really a data structure as it relies on underlying containers. It's used where the information is logically structured as a tree. In a BST, the data is logically structured as a sorted sequence - the end-user doesn't know or care that that's implemented via tree structures. This class is used where parent/child relationships are relevant to the application.

The underlying data is normally held in a similar way to how you'd build tree structures within a relational database - items have parent fields etc - though the library is decoupled from that by being a C++ policy-driven template. It works through a set of simple calls such as Get_Parent, Get_Next_Child and so on, which are usually trivial to implement.

I call the library an "XML tool", basically because it supports a view of the underlying tree that is similar to XML elements. You can traverse the whole tree, for example, and you will see begin "tags" and end "tags" for each node in the order you'd expect to see the tags in an XML file representing that tree. There's other traversal orders, such as "treeview" (preorder), and there's support for subscripting as well as simple traversal.

And there's support for summaries where every item gets a size (which can be zero, but not negative) and a running total is kept. I've used this e.g. for a tree-table control that I admittedly never finished. When an item is collapsed, it's total size summary for its descendants is forced to zero (with changes propogated up the tree) so that searches based on position within this view of the tree don't see those descendants. That makes it easy to find and iterate the currently visible items.

BTW - the unfinished GUI tree table control was never the most important application - it's just an easy one to visualise.


O(N) dequeue right? Thanks, but I'll find another implementation. The deque from the C++ Standard lib can do O(1) push and pop from both ends, and random access.

  • 2
    The deque from the C++ standard lib is a mutable data structure... Also, I'm certainly not trying to sell it to you.
    – GregRos
    Commented Jul 2, 2012 at 11:00
  • @GregRos: Mutable data structures are easily converted into immutable ones: Just don't call any of the mutating functions.
    – DeadMG
    Commented Jul 2, 2012 at 15:43
  • Ah, I was referring to immutability in the sense of Persistence
    – GregRos
    Commented Jul 2, 2012 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.