2026-07-22T12:37:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20437 2024-07-18T12:12:42Z ddc:004 open_access

Enumeration and Succinct Encoding of AVL Trees Chizewer, Jeremy Melczer, Stephen Munro, J. Ian Pun, Ava AVL trees analytic combinatorics succinct data structures enumeration 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 of 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremy Chizewer and Stephen Melczer and J. Ian Munro and Ava Pun 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.2 urn:nbn:de:0030-drops-204376 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.2 eng https://creativecommons.org/licenses/by/4.0/legalcode