lnstiblt flir Algebra und

In this paper, we give exact and asymptotic approximations for variance of the external path length in a symmeuic Patricia trie. The problem was open up to now. We prove that for the binary Pabicia trie, the variance is asymptotically equal to 0.37...·n + n P (lOg2 n) where n is the number of stored records and P (x) is a periodic function with a very small amplitude. This result is next used to show that from the practical (average) viewpoint, the Pabicia bie 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 tries) can be expected in practice to match the per-formance of more complicated, worst-case asymptotically better ones. 1