Re: 2-3-4 Trees

Noam Rotem <nrotem@johnbryce.co.il> writes:
> Recently, I was requested to write some code involving 2-3-4


There seems some confusion about the `2-3-4 trees' in the newsgroup.
I recently had to implement sets in a language, and did some research
in the world of trees. I came across this type of trees in the context
of (a,b)-trees (with a=2, and b=4).


> trees. Since all my efforts to find any material dealing with this
> data structure on the net failed, I developed my own version of those


It is true that not much information can be found on trees on the net.
Imho, the main reason is that these data structures are quite complex,
and only few people develop this type of code. On the other hand,
many libraries either use or provide some form of trees, so
implementations can be found.


> trees. It works, and looks good, but I'm still curious about the
> academic implementation taught and used in public. Can anyone send me


(a,b)-trees are explained in a number of books, including Sedgewick,
"Algorithms", Addison-Wesley 1988. Implementations are often build as
Red-Black trees (because (2,4)-trees are ugly to implement). One book
explaining an implementation is Cormen, Leierson and Rivest,
"Introduction to algorithms", McGraw-Hill 1990.


> a C/C++ / pseudo code / other implementation of 2-3-4 trees, or some
> theoretic general explanations?


I have a (2,4)-tree implementation in case you are interested. It uses
the insert algorithm as described in Sedgewick, but I had to invent
the delete algorithm myself (Sedgewick says something like "delete is
along the same lines as insert, and is not explained here").
--
Albert
--

Return to the comp.compilers page.
Search the comp.compilers archives again.