Digital search trees Recall that a digital search tree or DST is a hybrid of the digital trie and the binary search tree defined as follows. 1- p , independently of the others. Under the binary memoryless model, the number of segments formed so far is a random variable M n that is also the number of internal nodes of the companion dst built by the algorithm. By design, the dst is built of keys that obey Eq. It is also realized easily that the internal path length of the corresponding tree is equal to n .
Analysis starts with the random dst model.
Inversion will then be realized by an application of renewal theory. Let L m be the path length of a digital search tree built on m random strings according to the Bernoulli model. By bootstrapping, the functional equation is solved in larger and larger pseudo-cones. Then, mean, variance, and limit distribution follow for the Poisson model. The technical difficulties are rather formidable, but the results obtained are extremely precise.