Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world?

In this Cornell: http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html I read that splay trees are 'A good example is a network router'. But from rest of the explanation seams like network routers use hash tables and not splay trees since the lookup time is constant instead of O(log n).

share|improve this question
    
NB hash tables are only expected O(1) time. It can be significantly worse (but correct, so you may not notice) if you make an error in the hashing or collision resolution. A decent tree, however, gives you worst-case guarantees. –  delnan Oct 20 '12 at 22:36
    
I suspect splay trees actually perform surprisingly poorly in real life, because they generate writes to memory during ostensibly read-only operations. That makes life harder for compilers and caches, which are things you really want to have on your side for good performance. –  Tom Anderson Oct 21 '12 at 23:35
1  
A splay tree is O(n) worst-case guarantee per query -- it is amortized O(log n). However, its adaptive nature means that access to any given working set is amortized O(log(working set size)). Splay trees are appropriate for use cases that have strong key use locality, benefit from amortized performance guarantees, and are single-threaded (due to the update requirements mentioned by @TomAnderson). –  comingstorm Oct 23 '12 at 19:12
add comment

1 Answer

It is important to note that hash tables only have average access time of O(1). This means a particular operation could be much worse. Additionally, there are several requirements for properly formed hash trees:

  • Mostly empty - few hash algorithms perform well beyond 70% usage, and most recommend 50% usage.
  • Collision handling is complex - either having to use a list as the "stored value" or accepting a worst case linear search time
  • Hashing cost - you have to perform a hashing operation, which may or may not involve a lot of work

It sounds like the course mentions that in many routers these issues have been solved so they use a hash table for storage. However there are several advantages to splay trees

  • No overhead - if you allocate 10 MB to storage you get 10 MB worth of data without adjusting your run-times
  • Recent access preference - recent data is more easily accessed, and routers access more recent data frequently (new network nodes are likely to talk, and most networks are not used evenly)
  • Dups are fine - can be useful depending on what you are storing
  • Simple implementation - routers are typically run on fairly weak processors and are incredibly difficult to update, so simplicity is nice

Unfortunately this doesn't answer your question directly, but hopefully it sheds some light on why that is the case.

BTW, here are some notes on why routers may have moved away (these line up with advantages):

  • Storage sizes have gone up, due to the cost of RAM going down, ability to keep things in memory is easier
  • Hash tables when properly maintained have constant access to all elements
  • Hash tables can handle dupes if you need them to
  • Router manufacturers are typically long lived and can overcome complexity issues with time
share|improve this answer
    
Thanks Guvante! Even though it didn't answer my question still great information! –  Meena Oct 21 '12 at 1:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.