Home Original page

Balanced trees

Marko Rauhamaa marko at pacujo.net
Mon Mar 10 13:08:47 EDT 2014 
Chris Angelico <rosuav at gmail.com>:

> The only difference between a tree and a hash here is that the tree
> might be able to short-cut the comparisons. But if there are a whole
> bunch of songs with the same "song" and "user", then the tree has to
> compare (song->song? same; user->user? same; add_time->add_time?
> left/right) multiple times. So what you're saying is that the hash
> table has consistency but the tree could do better or could do worse.
> (Imagine, worst case, all one million records have the same
> song/user/add_time and you need to do twenty comparisons involving
> four fields. That's gotta be worse than one hashing of five fields.)

You are right that in the end there probably is an equality test
involving all fields of the key. However, the intermediate comparisons
are often dealt with much more immediately. For example, to compare the
words "hello" and "world", you only need to look at the first letter.

Anyway, this whole debate is rather unnecessary since every developer is
supposed to have both weapons in their arsenal.


Marko
More information about the Python-list mailing list