Logarithmic guarantees for randomized search trees

Question

In this paper [1], "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:

1. 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.
2. I understood the paragraph wrongly and they actually mean that the priority generation is controlled by the user not just seen by the user.

[1] https://faculty.washington.edu/aragon/pubs/rst96.pdf

Answer 1

Let's consider a different example: a hash table. While usually the hash function is fixed in advance, it is also possible for it to be chosen randomly when the hash table is initialized.

If we want to mount a Denial of Service attack on a hash table, we need to feed it many keys that hash to the same value. If the hash function is weak and known, then we can easily do it. If the hash function is weak and unknown, then it could be difficult or even impossible.

When the authors say that the priorities are kept hidden from the user, they mean that the randomness used in the data structure is not "public". In our hash table example, it means that the user of the hash table doesn't know which hash function was chosen. If the user knew the hash function then she could mount a DoS attack. If she doesn't, then such an attack becomes much more difficult.

In practice we don't necessarily think of the user as malicious; however, we want a guarantee on the running time which is independent of how the data structure is used. Suppose that we use a treap or a randomized BST in some algorithm, in a very specific way. If the algorithm has access to the randomness—for example, if it is fixed—then perhaps its specific access pattern results in bad performance. However, if the algorithm acts independently of the randomness, then bad performance only happens with small probability.