Digital Search Trees Revisited

Publisher Website
Google Scholar
Abstract
Several algorithms have been proposed which build search trees using digital properties of the search keys. A general approach to the study of the average case performance of such algorithms is discussed, with particular attention to the analysis of the digital search tree structures of Coffman and Eve. Specifically, the method leads to the solution of a problem left open by Knuth, finding the average number of nodes in digital search trees with both sons null. The paper may be of interest as a survey and tutorial treatment of the analysis of the three primary digital tree search methods: digital search trees, radix search tries, and Patricia tries. To insert a new record with a new value v, we search, then replace the null pointer that caused termination with a pointer to the new record. The analysis of the perform- ance of this method is well-known: if records with keys from a random permutation ofN elements are successively inserted into an initially empty tree, then the expected number of nodes examined in a successful search in the resulting tree is

This publication has 7 references indexed in Scilit: