In our previous lecture, we explored four different usage models for binary search trees and saw that each one counseled the use of a different data structure. But what if there was one single BST that could achieve all these goals? Turns out we have such a data structure - the splay tree - and it just might be (to within constant factors) the best possible BST anyone could ever make. (At least, for some definition of "best.")
Readings
- Daniel Sleator and Robert Tarjan. Self-Adjusting Binary Search Trees.
Links