Analysis of digital search trees incorporated with paging∗
Received: 1 February 2016
Accepted: 10 January 2017
Ordinary digital search trees (DSTs) stores one word in each of its internal nodes and leaves, but a DST with paging size b allows storing b words in the leaves, which corresponds to pages in auxiliary storage. In this paper, we analyse the average number of nodes, the average node-wise path length and 2-protected nodes in DSTs with paging size b. We utilize recurrence relations, analytical Poissonization and de-Poissonization, the Mellin transform, and complex analysis. We also compare the storage usage in paged DSTs to that in DSTs. For example, for b = 2,3,4,5,6, the approximate average number of nodes in paged DSTs is, respectively, 82%, 67%, 55%, 47%, 41% of the size of DSTs (when b = 1). Thus the results are nontrivial and interesting for computer scientists.
Mathematics Subject Classification: 05C05 / 60C05
Key words: Random trees / paged digital search trees / singularity analysis
© EDP Sciences 2017