A traditional cost measure for binary search trees is given by weighted path length, which measures the expected cost of a single random search. In this paper, we investigate a generalization, the k-cost, which is suitable for applications involving independent parallel processors each utilizing a common search tree. The k-cost is defined to be the expected value of the maximum length of the search paths encountered during the course of k independently performed random searches. For example, if k s 1, then the k-cost represents the traditional weighted path length. Our results include efficient algorithms for constructing binary search trees having near optimal k-cost. An interesting feature of one of our algorithms concerns the fact that it constructs a search tree that simultaneously has near optimal k-cost for all k; in fact, the structure of this tree is determined only by the order permutation of the sequence of probability weights that are to be assigned to the tree nodes. This stands in contrast to an example which shows that a tree which Ε½ . is precisely optimal relative to weighted path length 1-cost can have k-cost which is exponentially greater than the k-cost of the optimal tree. We also investigate connections between splaying and k-cost. In pursuing this connection we define a problem, the curator problem, which is approximately dual to the problem of optimal k-cost, and then use this duality to elucidate certain aspects of the dynamic optimality conjecture for splay trees.