Re: 2-3-4 Trees

"Declan Cox" <>
23 Dec 1997 23:00:29 -0500

          From comp.compilers

Related articles
2-3-4 Trees (Noam Rotem) (1997-12-17)
Re: 2-3-4 Trees (1997-12-19)
Re: 2-3-4 Trees (1997-12-19)
Re: 2-3-4 Trees (Declan Cox) (1997-12-23)
| List of all articles for this month |

From: "Declan Cox" <>
Newsgroups: comp.compilers
Date: 23 Dec 1997 23:00:29 -0500
Organization: Iona Technologies
References: 97-12-140
Keywords: theory
Comments: Authenticated sender is <dcox@operation>

> Hello world!
> Recently, I was requested to write some code involving 2-3-4
> trees. ...


> [I never heard of a 2-3-4 tree. What is it? -John]

A 2-3-4 tree is an example of a technique of balancing binary trees.
Such a tree has nodes which allow multiple keys and links. e.g., a
3-node has 2 keys and 3 links - one for all records with keys smaller
than both its keys, one for all records with keys in between it's two
keys and one for records with keys larger than both its
keys. Similarly a 4-node has three keys and four links. Each of its
keys define the intervals of its 4 links. (standard binary trees nodes
could be called 2-nodes). For a more detailed description along with
sample code for implementing such algorithms see Robert Sedgewick's
classic text "Algorithms" published by Addison Wesley (gives examples
in Pascal, there are now however versions in C & C++ titled
"Algorithms in C" & "Algorithms in C++" respectively).


Declan Cox
Iona Technologies PLC
8-10 Pembroke st. lower
Dublin 2

Tel : +353-1-6625255
Fax : +353-1-6625244

Post a followup to this message

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