Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T02:28:55.383Z Has data issue: false hasContentIssue false

DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION

Published online by Cambridge University Press:  14 December 2015

Ravi Kalpathy
Affiliation:
Department of Mathematics and Statistics, University of Massachusetts Amherst, MA 01003, USA E-mail: rkalpathy@math.umass.edu
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, DC 20052, USA E-mail: hosam@gwu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We revisit the random m-ary search tree and study a finer profile of its node outdegrees with the purpose of exploring possibilities of data structure compression. The analysis is done via Pólya urns. The analysis shows that the number of nodes of each individual node outdegree has a phase transition: Up to m = 26, the number of nodes of outdegree k, for k = 0, 1, …, m, is asymptotically normal; that behavior changes at m = 27. Based on the analysis, we propose a compact m-ary tree that offers significant space saving.

Information

Type
Research Article
Copyright
Copyright © Cambridge University Press 2015