Notes:

• Proves that the bit reversal permutation on [n] is a worst-case sequence for all binary search tree (BST) data structures. In other words, on this sequence upper and lower bounds meet.
• Shows that every the optimal offline BST has the same expected cost on a random sequence as the optimal static one. In other words, on such sequences upper and lower bound meet (as well).
• For Wilber's 1st bound, the intuitive reason why even the optimal lower bound tree may produce a weak bound has to do with the fact that a very long access sequence may have very different access pattern on a given range of elements in different sections of the sequence.

Ideas:

• How would the expression for Wilber's 1st bound change, if we allow that the lower bound tree by changed (via rotations) inbetween accesses?