Abstrakt. Vi anser att kortfattade eller utrymmeseffektiva representationer av träd som effektivt stöder en mängd olika navigeringsåtgärder. Vi fokuserar på statiska ordinala träd, det vill säga godtyckliga statiska rotade träd där barnen till varje nod är beställda. Verksamheten består huvudsakligen av en sammanslagning av de åtgärder som stöds av tidigare koncisa representationer [Jacobson 1989; Munro och Raman 2001; Benoit m.fl. 1999 ] som vi lägger till nivå-föräldra-driften. Vår representation tar 2n + o(n) bitar för att representera ett n-node träd, som ligger inom o(n) bitar av den information-teoretiska minimum, och stöder alla operationer i O(1) tid på RAM-modellen. Dessa operationer ger också en kartläggning från n noder av trädet till heltal {1,..., n}. Förutom de befintliga motivationerna för att studera sådana datastrukturer, är vi motiverade av problemet med att representera XML-dokument kompakt så att XPath frågor kan stödjas effektivt.
På så sätt kan ett n-nodeträd representeras av 2n + o(n) bitar, samtidigt som O(1) tid för de flesta avläsningsåtgärder på ett träd REF.
Succinct ordinal trees with level-ancestor queries
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}