Both these trees try to keep the most frequently accessed element at the top. Is there any difference between these two trees?

  • 1
    How do you get the optimal structure? From Wikipedia on optimal binary search trees "If we do not know the sequence in which the elements in the tree will be accessed in advance, we can use splay trees which are asymptotically as good as any static search tree we can construct for any particular sequence of lookup operations." – user40980 Feb 26 '14 at 3:19

A Splay Tree is a specific variation of binary tree, specifying certain attributes of how the tree should be implemented. An Optimal Binary Search Tree is any binary tree for which the lookup cost is minimized.

One describes the implementation, the other describes the result.

So your question is a bit like asking "What's the difference between a Rally Car and a Fast Car?" The answer is that the question doesn't really make sense.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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