> Serhiy Storchaka: Yes, but it is still O(log n) worst case. Even in the
> worst case rebalancing, you only need to walk up/down rotating/spliting
> every node in your path. As the tree height is guaranteed to be x * log n
> (x from 1 to 2, depending on the algorithm), the rebalancing operation is
> aways limited by O(log n).

Agree. However I think that for large enough data a balanced tree is slower 
than a hashtable with any slow hash.