A characterization of digital search trees from the successful search viewpoint (Q1183573): Difference between revisions

The author is interested in studying the average complexity of the successful search in digital trees. He assumes that a sequence of elements is an independent sequence of Bernoulli trials and that the \(i\)- th digit in a key occurs independently of the other digits. In previous papers, the author has investigated radix search trees and Patricia tries from this point of view. He uses the method of generating functions and establishes a relationship between the derivatives of a generating function, defined by a rather sophisticated recurrence equation, and the moments of a successful search. It is well-known that the number of digits examined during a random successful search is \(c_ 1\log n+O(1)\). By solving the recurrence asymptotically, the author gets a more precise characterization of the form \(c_ 1\log n+c_ 2+O(\log n/n)\). Finally, he compares the three types of digital trees: The best constant in the mean value is achieved for the digital search tree, whereas the best variance is for Patricia tries. Unfortunately, the paper is not self- contained and, therefore, difficult to read.