AA with complex keytype?

[Frits van Bommel]

Stewart Gordon wrote:
> Manfred Nowak Wrote:
> 
>> Frits van Bommel wrote
> <snip>
>>> (do current AAs use unbalanced trees?  I have no idea, I just 
>>> know they use _some_ form of trees)
>> They are unbalanced.  Look at phobos/internal/aaA.d:278 and 
>> following lines.
> 
> Balancing the trees on the fly would be inefficient.  But rehash ought to balance them while it's at it.

There are several well-known methods of efficiently keeping binary trees 
(reasonably) balanced. Off the top of my head there are AVL trees and 
red-black trees, but those definitely aren't the only ones.

For implementing a hash-table bucket this is probably not necessary, 
though. There typically shouldn't be very much elements in a bucket.