8/11 Why do people ever use trees instead of hash tables? If I have
a hash table which grows dynamically to stay less than half full
then insert/query/delete are all expected constant time. On the
other hand, if I use a tree which is perfectly balanced then
insert/query/delete all take log(n). Do people use trees just
because they are better in the worst case? Thanks.
\_ Trees let you search for key ranges: if you want to find all
the elements with keys between 5 and 13, that's fast in a tree
but slow in a hash table.
\_ Along the same lines as the post above, you can do an incremental
search in trees. For example, if you have a bunch of command names
in a tree and the user types the first three letters you can find
all the k matching commands in k+log(n) time. -emin
\_ But why use trees when God created SkipLists?
\_ Not God. Phillip "Edward" Nunez!
\_ Ease of coding. Sometimes it just doesn't matter and isn't
worth any extra effort.
\_ Take 186 and become enlightened.
\_ I have heard trees (or tries) are used in database and disk
heavy applications, but except for the 2 comments above, why
not just use hash tables? I'd be happy if you could give me
a simple example, or point me to a good book or URL. I'm no
a student so taking 186 is not an option.
\_ Read any data structures book. And look up "tradeoff". |
http://csua.com/feed/