In this paper we present probabilistic algorithms over random binary search trees such that: a) the insertion of a set of keys in any fixed order into an initially empty tree produces always a random tree; b) the deletion of any key of a random tree results in a random tree; c) the random choices made by the algorithms are based upon the sizes of the subtrees of the random tree, an information that can be used for rank searches, for instance; and d) the cost, measured as the number of visited nodes, of any elemental operation is the same as the cost of the standard deterministic version, with less than two expected rotation-like operations per update.