StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Ok, I guess there wasn't a lot of references or research for answering this question. Instead I've taken the time to try your different ideas and trees. I didn't find anything a lot better than RB trees, but perhaps that's just search bias.</p> <p>The RB tree can be (insertion) balanced with four simple rules, as <a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps" rel="noreferrer">shown by Chris Okasaki</a>:</p> <pre><code>balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d) balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d) balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d) balance T a x b = T B a x b </code></pre> <p>AVL trees can be balanced in a similar pattern matching way. However the rules don't compress as well:</p> <pre><code>balance T (T (T a x b dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d 0) 0 balance T a x (T b y (T c z d dz) 1 ) 2 = T (T a x b 0) y (T c z d dz) 0 balance T (T a x (T b y c 1 ) 1 ) z d (-2) = T (T a x b -1) y (T c z d 0) 0 balance T (T a x (T b y c (-1)) 1 ) z d (-2) = T (T a x b 0) y (T c z d 1) 0 balance T (T a x (T b y c _ ) 1 ) z d (-2) = T (T a x b 0) y (T c z d 0) 0 balance T a x (T (T b y c 1 ) z d (-1)) 2 = T (T a x b -1) y (T c z d 0) 0 balance T a x (T (T b y c (-1)) z d (-1)) 2 = T (T a x b 0) y (T c z d 1) 0 balance T a x (T (T b y c _ ) z d (-1)) 2 = T (T a x b 0) y (T c z d 0) 0 balance t = t </code></pre> <p>As AVL trees seams to generally be considered inferior to RB trees, they are probably not worth the extra hassle.</p> <p>AA trees could theoretically be balanced nice and easily by:</p> <pre><code>balance T n (T n a x b) y c = T n a x (T n b y c) -- skew balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split balance T n a x b = T n a x b </code></pre> <p>But unfortunately Haskell don't like the overloading of <code>n</code>. It is possible that a less standard implementation of AA trees, not using ranks, but something more similar to R and B, would work well.</p> <p>Splay trees are difficult because you need to focus on a single node, rather than the static structure of the tree. It can be done by <a href="http://www.haskell.org/pipermail/haskell-cafe/2010-October/085377.html" rel="noreferrer">merging insert and splay</a>.</p> <p>Treaps are also uneasy to do in a functional environment, as you don't have a global random generator, but need to keep instances in every node. This can be tackled by <a href="http://hpaste.org/46259/treaps?pid=46259&lang_46259=Haskell#17" rel="noreferrer">leaving the task of generating priorities to the client</a>, but even then, you can't do priority comparison using pattern matching.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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