[erlang-questions] How would you do 100 ifs?

Richard Carlsson <>
Tue Nov 15 15:53:31 CET 2011


On 11/15/2011 03:45 PM, Robert Virding wrote:
> If you want a more complete implementation of Red-Black trees then
> look at:
>
> https://github.com/rvirding/rb
>
> The module is dict/orddict compatible. One of these days I will fix
> the documentation and add it to the distribution. The algorithm for
> Red-Black trees is a little complex in that it works on both
> branches. I also have a simpler tree based on an algorithm by Arne
> Andersson which is like a one-sided rb-tree. It is almost as fast and
> a better base for specialisation because of its simplicity.
>
> One thing is a little unclear to me and that is how static is your
> "table"? Is compile-time static, or initialisation static? If it
> compile-time static then it is faster to do the binary tree "by hand"
> as clauses in code.
>
> Robert
>
> P.S. This is the same Arne Andersson whose algorithm is used in
> gb_trees, probably same algorithm but we read different papers
> presenting it.

Arne's General Balanced Trees are different from his perhaps more well 
known AA trees (http://en.wikipedia.org/wiki/AA_tree). A great advantage 
from other kinds of balanced trees is that they store no extra balancing 
information per node, so in a language like Erlang they save one machine 
word per node compared to an RB-tree of the same size.

    /Richard



More information about the erlang-questions mailing list