Handbook of Data Structures and Applications, 2nd Edition

38

Succinct Representation of Data Structures^*

J. Ian Munro

University of Waterloo

S. Srinivasa Rao

Seoul National University

38.1Introduction

38.2Bitvector

38.3Succinct Dictionaries

Indexable Dictionary•Fully Indexable Dictionary• Dynamic Dictionary

38.4Tree Representations

Binary Trees•Ordinal Trees•Cardinal Trees•Dynamic Binary Trees

38.5Graph Representations

38.6Succinct Structures for Indexing

38.7Permutations and Functions

Permutations•Functions

38.8Partial Sums

38.9Arrays

Resizable Arrays• Dynamic Arrays

38.10Conclusions

References

38.1Introduction

Although computer memories, at all levels of the hierarchy, have grown dramatically over the past few years, increased problem sizes continues to outstrip this growth. Minimizing space is crucial ...