DIGITAL SEARCH-TREES REVISITED

被引:80
作者
FLAJOLET, P [1 ]
SEDGWICK, R [1 ]
机构
[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544
关键词
COMPUTER PROGRAMMING - Algorithms - MATHEMATICAL TECHNIQUES - Trees;
D O I
10.1137/0215054
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:748 / 767
页数:20
相关论文
共 17 条
[1]   FILE STRUCTURES USING HASHING FUNCTIONS [J].
COFFMAN, EG ;
EVE, J .
COMMUNICATIONS OF THE ACM, 1970, 13 (07) :427-&
[2]  
DAVIES E, 1978, INTEGRAL TRANSFORMS
[3]  
Flajolet P., 1979, Theoretical Computer Science, V9, P99, DOI 10.1016/0304-3975(79)90009-4
[4]  
FLAJOLET P, 1983, PARTIAL MATCH RETRIE
[5]  
FLAJOLET P, UNPUB BIT
[6]  
FLAJOLET P, UNPUB MELLIN TRANSFO
[7]  
FLAJOLET P, 1983, ASYMPTOTIC EVALUATIO
[8]  
Hardy G. H., 1960, INTRO THEORY NUMBERS
[9]  
Knuth D. E., 1973, ART COMPUTER PROGRAM
[10]  
KNUTH DE, 1978, P K NED AKAD A MATH, V81, P238