- 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.
- How would the expression for Wilber's 1st bound change, if
we allow that the lower bound tree by changed (via rotations)