On Mon, 16 Oct 2000 11:28:37 PDT, Carl Wuebker wrote:
> I'd like to put in a pitch for RFC 124 in Perl 6. Balanced binary
>trees (such as AVL or red-black trees) allow O(log2 n) insertion, searching,
>outputting ranges of keys & deletion. I wouldn't want to touch existing Perl
>hashes, but it would be very useful to be able to associate a sort routine
>with certain hashes & have those hashes maintained as balanced binary trees.
>The speed advantage would be in not having to sort keys every time the hash
>is changed.
But isn't there going to be a large overhead, in populating such a
"hash"? Doesn't the tree have to be reorganized every time you add a
single new entry?
The O(...) of the algorithm doesn't say everything. It doesn't mention
the multiplication constant.
Reading can be fast, I grant you.
--
Bart.
