Digital Search Trees Revisited
Authors:
- Philippe FlajoletPFPhilippe Flajolet
- Robert SedgewickRSRobert Sedgewick
- 1 August 1986
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (3) , 748-767
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 Coflman 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.Keywords
This publication has 7 references indexed in Scilit:
- Approximate counting: A detailed analysisBIT Numerical Mathematics, 1985
- The number of registers required for evaluating arithmetic expressionsTheoretical Computer Science, 1979
- Data Movement in Odd-Even MergingSIAM Journal on Computing, 1978
- Integral Transforms and Their Applications1978
- Problems and Theorems in Analysis1976
- A note on growing binary treesDiscrete Mathematics, 1973
- File structures using hashing functionsCommunications of the ACM, 1970