Settling the relationship between Wilber's bounds for dynamic optimality

Victor Lecomte, Omri Weinstein

In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence $X\in [n{]}^m$. Both bounds play a c…