Balanced trees

[Dan Stromberg]

On Sun, Mar 9, 2014 at 1:27 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Dan Stromberg <drsalists at gmail.com>:
>
>> On Sat, Mar 8, 2014 at 1:21 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>>> If I had to choose between a hash table and AVL (or RB) tree in the
>>> standard library, it would definitely have to be the latter. It is more
>>> generally usable, has fewer corner cases and probably has an equal
>>> performance even in hash tables' sweet spot.
>>
>> Actually, in the performance comparison I mentioned previously, I
>> compared Python dict's to a bunch of different balanced trees and one
>> unbalanced tree. The dictionary was much faster, though granted, it
>> was the only one in C.
>
> Yes, that is one major detail. There must be many more.

This is not just a detail: O(1) tends to be beat O(logn) pretty easily
for large n.