On the balance property of Patricia tries: External path length viewpoint

AbstractIn this paper, we give exact and asymptotic approximations for the variance of the external path length in a symmetric Patricia tree. The problem was open up to now. We prove that for the binary Patricia tree, the variance is asymptotically equal to 0.37 …n+nP(log2n) where n is the number of stored records and P(x) is a periodic function with a very small amplitude. This implies that the external path length is asymptotically equal to n·log2n with probability one (i.e., almost surely). These results are next used to show that from the practical (average) viewpoint, the Patricia tree does not need to be restructured in order to keep it balanced. In general, we ask to what extent simpler and more direct algorithms (for digital search trees) can be expected in practice to match the performance of more complicated, worst-case asymptotically better ones