Re: 2-3-4 Trees

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


[snip]


> [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).


Regards
Declan.


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


Tel : +353-1-6625255
Fax : +353-1-6625244
Email: dcox@iona.ie
URL : http://www.iona.com
--

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