Digital Search Trees Revisited (Q3751029)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3988729
Language Label Description Also known as
default for all languages
No label defined
    English
    Digital Search Trees Revisited
    scientific article; zbMATH DE number 3988729

      Statements

      Digital Search Trees Revisited (English)
      0 references
      0 references
      0 references
      1986
      0 references
      analysis of algorithms
      0 references
      path length
      0 references
      asymptotic analysis
      0 references
      average case performance
      0 references
      digital search tree
      0 references
      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.
      0 references

      Identifiers