In this paper , "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being inserted into the tree.
The authors assume that randomness is "hidden" from the user:
All expectations are with respect to randomness that is "controlled" by the update algorithms. For the time being we assume that the priorities are kept hidden from the "user." This is necessary to ensure that a randomized search tree is transformed into a randomized search tree by any update. If the user knew the actual priorities it would a simple matter to create a very "non-random" and unbalanced tree by a polynomial number of updates.
I don't actually understand what is meant by that. Specifically, I don't understand what the user might be able to do to affect the runtime by observing the generated priorities. My ideas of trying to understand that are:
- The user might be able to provide keys in certain order to make the resulting trees unblanaced! However, I don't think this is right because the priorities are not generated based on key values.
- I understood the paragraph wrongly and they actually mean that the priority generation is controlled by the user not just seen by the user.