DIGITAL SEARCH TREES REVISITED.

Philippe Flajolet, Robert Sedgewick

Research output: Contribution to journalArticle

79 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)748-767
Number of pages20
JournalSIAM Journal on Computing
Volume15
Issue number3
DOIs
StatePublished - Jan 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'DIGITAL SEARCH TREES REVISITED.'. Together they form a unique fingerprint.

  • Cite this