Databases
StackOverflow2013
Postsdbo
POImplement an immutable deque as a balanced binary tree?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImplement an immutable deque as a balanced binary tree?
    primarykey
    data
    text
    <p>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.</p> <p>There seem to be different ways of doing this. AFAIK, <a href="https://stackoverflow.com/questions/1993760/how-is-memory-efficient-non-destructive-manipulation-of-collections-achieved-in-f/1993931#1993931">immutable data structures are generally hierarchical</a>, so that major parts of it can be reused after modifying operations such as the insertion or removal of an item.</p> <p>Eric Lippert has <a href="http://blogs.msdn.com/b/ericlippert/archive/2008/01/22/immutability-in-c-part-10-a-double-ended-queue.aspx" rel="nofollow noreferrer">two</a> <a href="http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx" rel="nofollow noreferrer">articles</a> on his blog about this topic, along with sample implementations in C#.</p> <p>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 <em>front</em>) and on the very "right" (the <em>back</em>) of the tree?</p> <pre><code> o / \ … … / \ … … / \ / \ front --&gt; L … … R &lt;-- back </code></pre> <p>Additionally, the tree would be kept reasonably balanced with rotations:</p> <ul> <li>right rotations upon insertion at the front or upon removal from the back, and</li> <li>left rotations upon removal from the front or insertion at the back.</li> </ul> <p>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?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USstakx
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. USJunx
      1. VTFavorite
    1. COI've written a basic sample implementation for front insertion and removal: [C# source code](http://gist.github.com/479471#)
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. USstakx
    2. COsince the deque is immutable, why not using an array?
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. USDave O.
    3. CO@Dave: because ideally, I would want to re-use as many items from the initial (unmodified) deque in the new (modified) deque as possible upon manipulation operations. This seems hardly possible with an array.
      singulars
      1. POImplement an immutable deque as a balanced binary tree?
      1. USstakx
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload