Laws of large numbers and tail inequalities for random tries and PATRICIA trees

摘要

We consider random tries and random PATRICIA trees constructed from n independent strings of symbols drawn from any distribution on any discrete space. If Hn is the height of this tree, we show that Hn/E{Hn} tends to one in probability. Additional tail inequalities are given for the height, depth, size, internal path length, and profile of these trees and ordinary tries that apply without any conditions on the string distributions—they need not even be identically distributed.