2023/11/27 by Jeremy Chizewer, Chizewer, Jeremy, Stephen Melczer +5
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2311.15511
openalex publication_date 2023/11/27 · openalex created_date 2023/11/29 · openalex updated_date 2026/07/28
We use a novel decomposition to create succinct data structures -- supporting a wide range of operations on static trees in constant time -- for a variety tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class of AVL trees, we further derive asymptotics for the information-theoretic lower bound on the number of bits needed to store tree classes whose generating functions satisfy certain functional equations. In particular, we prove that AVL trees require approximately 0.938 bits per node to encode.