We've been operating under the assumption that a balanced BST that has worst-case $O(\log n)$ lookups is, in some sense, an "optimal" binary search tree. In one sense (worst-case efficiency) these trees are optimal. However, there are other perspectives we can take on what "optimal" means, and they counsel toward other choices of tree structures - weight-balanced trees, finger search trees, and Iacono's working set structure.
Readings
- Kurt Melhorn. Nearly-Optimal Binary Search Trees.
- John Iacono. Alternatives to Splay Trees with $O(\log n)$ Worst-Case Access Times.
Links