A probabilistic analysis of the height of tries and of the complexity of triesort

DOI10.1007/BF00264248zbMATH Open0555.68037MaRDI QIDQ760797FDOQ760797

Authors: Luc Devroye 

Publication date: 1984

Published in: Acta Informatica (Search for Journal in Brave)

Recommendations

• An Analysis of the Height of Tries with Random Weights on the Edges
• Profiles of Tries
• Towards a complete characterization of tries
• Publication:4508387
• A note on the asymptotic behavior of the depth of tries

zbMATH Keywords

binary triesaverage heighttriesort

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Laws of the iterated logarithm for order statistics of uniform spacings
• A note on the average depth of trees
• A note on the analysis of extendible hashing
• On the average height of trees in digital search and dynamic hashing
• Title not available (Why is that?)

Cited In (29)

• Title not available (Why is that?)
• Algorithms and Data Structures
• The height of list-tries and TST
• Brownian motion and algorithm complexity
• On the stack-size of general tries
• Analysis of random LC tries
• Exact and asymptotic distributions in digital and binary search trees
• Title not available (Why is that?)
• Dichotomic Selection on Words: A Probabilistic Analysis
• \(D\cdot E\cdot K=(100)_8\)
• A note on the probabilistic analysis of patricia trees
• Asymptotic properties of keys and functional dependencies in random databases
• Rounding of continuous random variables and oscillatory asymptotics
• An Analysis of the Height of Tries with Random Weights on the Edges
• Maximum likelihood analysis of algorithms and data structures
• ON CLIMBING TRIES
• Smoothed heights of tries and patricia tries
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Upper tail analysis of bucket sort and random tries
• Upper tail analysis of bucket sort and random tries
• Title not available (Why is that?)
• The stack-size of tries: A combinatorial study
• On the height of digital trees and related problems
• A theoretical look at \textsc{Electre Tri}-nB and related sorting models
• New results on the size of tries
• Expected worst-case partial match in random quadtries
• On tries, contention trees and their analysis
• The properties of random trees
• How many random questions are necessary to identify \(n\) distinct objects?

This page was built for publication: A probabilistic analysis of the height of tries and of the complexity of triesort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760797)