The -Version of Binary Search Trees: An Average Case Analysis

Following a suggestion of Cichoń and Macyna, binary search trees are generalized by keeping (classical) binary search trees and distributing incoming data at random to the individual trees. Costs for unsuccessful and successful search are analyzed, as well as the internal path length. 1. Introduction Cichoń, together with his coauthor Macyna, had the seminal idea [1] to generalize approximate counting to approximate counting with counters. While in the original version [2] a stream of letters (a word) is dealt with a counter in a certain way (that is of no interest here), the new version uses counters and chooses for each letter one of these counters (with probability ), where it is dealt with as usual. The result of the procedure is the sum of the individual results of the counters. This fundamental idea should, however, not be restricted to approximate counting! Indeed, it can be considered within a variety of different contexts. In this paper, the fundamental idea is applied to binary search trees. They are very well understood and described in classic books such as [3, 4], with plenty of backward pointers to the older literature due to Lynch, Hibbard, Louchard, Brown, Shubert, and many others. We assume that, instead of just one, binary search trees are kept, and for each element, when inserting it, a decision is made to which of the trees it is being sent. Of course, for algorithmic purposes, this choice must be deterministic, so that one knows in which tree to search. However, for the analysis, it is assumed that each tree is equally likely and will be selected with probability . Almost all the information about binary search trees that is known to this day can be found in the encyclopedic books [3, 4]. We only mention that they originate from random permutations (typically of ); a new element is compared to the root and, if there is no space for it, is moved to the left/right if it is smaller/larger than the root; then the process continues. A binary search tree is used as a data structure. It is, thus, essential that one can find existing elements in a reasonable number of steps and also get the information that a searched element is not present after a small number of comparisons. This is the first paper about binary search trees, and the hope is that many more will be written in the future, by various specialists. Thus, no completeness is aimed at. Three parameters are studied. The cost for inserting a new element into the trees, which is related to the cost of unsuccessful search, then the cost for successful search, which is the average of