On Fri, 13 Jul 2001, Krishnaswami, Neel wrote:
> He has some timing data comparing splay trees, balanced binary 
> trees, Patricia tries, and red-black trees in his paper "Fast 
> Mergeable Integer Maps." To summarize, red-black trees were the 
> fastest on lookup, and second-fastest on insertion. But they don't
> perform very well on the merge operation. (These are all fairly
> tuned implementations, though.)

As usual, never trust statistics that you haven't faked yourself...

Such things can be pretty language and compiler dependent. At least
what concerns Patricia trees, I can assert that they really perform
very well in OCaml. This is obviously not true for red-black trees:
on my simple tests with random numbers, insertion took longer than with
balanced binary trees, and lookup also didn't seem competitive. Anyway,
I don't claim that my statistics are faked better than his... ;)

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr