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

  • 2
    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, 2014 at 3:19

1 Answer 1


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.

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