### Patricia tries again revisitedPatricia tries again revisited

Access Restriction
Subscribed

 Author Szpankowski, Wojciech Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The Patricia trie is a simple modification of a regular trie. By eliminating unary branching nodes, the Patricia achieves better performance than regular tries. However, the question is: how much on the average is the Patricia better? This paper offers a thorough answer to this question by considering some statistics of the number of nodes examined in a successful search and an unsuccessful search in the Patricia tries. It is shown that for the Patricia containing $\textit{n}$ records the average of the successful search length $\textit{Sn}$ asymptotically becomes $1/\textit{h}1$ · ln $\textit{n}$ + $\textit{O}(1),$ and the variance of $\textit{Sn}$ is either var $\textit{Sn}$ = $\textit{c}$ · ln $\textit{n}$ + $\textit{0}(1)$ for an asymmetric Patricia or var $\textit{Sn}$ = $\textit{0}(1)$ for a symmetric Patricia, where $\textit{h}1$ is the entropy of the alphabet over which the Patricia is built and $\textit{c}$ is an explicit constant. Higher moments of $\textit{Sn}$ are also assessed. The number of nodes examined in an unsuccessful search $\textit{Un}$ is studied only for binary symmetric Patricia tries. We prove that the $\textit{m}th$ moment of the unsuccessful search length $\textit{EUmn}$ satisfies $lim\textit{n}→∞$ $\textit{EUmn}/log\textit{m}2\textit{n}$ = 1, and the variance of $\textit{Un}$ is var $\textit{Un}$ = 0.87907. These results suggest that Patricia tries are very well balanced trees in the sense that a random shape of Patriciatries resembles the shape of complete trees that are ultimately balanced trees. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 4 Page Count 21 Starting Page 691 Ending Page 711

#### Open content in new tab

Source: ACM Digital Library