Re: 2-3-4 Trees

hat@se-46.wpa.wtb.tue.nl (Albert Theo Hofkamp)
19 Dec 1997 00:18:36 -0500

          From comp.compilers

Related articles
2-3-4 Trees nrotem@johnbryce.co.il (Noam Rotem) (1997-12-17)
Re: 2-3-4 Trees bart@time.cirl.uoregon.edu (1997-12-19)
Re: 2-3-4 Trees hat@se-46.wpa.wtb.tue.nl (1997-12-19)
Re: 2-3-4 Trees dcox@iona.com (Declan Cox) (1997-12-23)
| List of all articles for this month |

From: hat@se-46.wpa.wtb.tue.nl (Albert Theo Hofkamp)
Newsgroups: comp.compilers
Date: 19 Dec 1997 00:18:36 -0500
Organization: Compilers Central
References: 97-12-140
Keywords: theory

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
--


Post a followup to this message

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