std::map and std::set based on AVL, not RB trees.

[Chris Jefferson]

Daniel K. O. wrote:
> Hello.
> 
> Some months ago, while having nothing special to do, I modified the 
> libstdc++'s RB tree - used in the associative containers - into an AVL 
> tree.

First of all, let me say I found this interesting, and I intend to look 
into it more carefully when I have some time :)

A quick early comment, not specifically related to your code, is that 
the C++ standard is quite tight on the requirements of various 
functions. In particular, insert(t,p) (for a std::set), given value t 
and iterator p must be "amoritzed constant time if t is inserted right 
after p". Do AVL trees provide this? I thought that they didn't, but I 
could be wrong..

Chris