2014/05/31 by Ravi Kalpathy, Hosam Mahmoud
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Compression (physics) #Computability, Logic, AI Algorithms #Data structure #Node (physics) #Search tree #Space (punctuation) #Tree (set theory) #Tree structure #math.PR
paper · pdf · doi:10.1017/s0269964815000303
published as Prob. Eng. Inf. Sci. 30 (2015) 113-123
arxiv created 2014/12/28 · openalex publication_date 2015/12/14 · arxiv updated 2015/12/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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.