2007.09.03 | Gerth Stølting Brodal

Srinivasa Rao Satti
MADALGO

Succinct representations of trees

Abstract:

Trees are one of the most fundamental structures in computing. They are
used in almost every aspect of modeling and representation for explicit
computations. Standard representations of trees using pointers are quite
wasteful of space, and could account for the dominant space cost in
applications such as storing a suffix tree. For example, a standard
representation of a binary tree on n nodes uses 2n pointers or 2n log n
bits. This is a factor of log n more than the minimum number ofbits
necessary, as there are less than 4^n distinct binary trees on n nodes.
Also, this only supports finding theleft/right child of a node
efficiently.

In this talk,starting with a brief introduction to succinct or highly
space efficient data structures, I will present some tree representations
that take only 2n + o(n) bits and support various useful queries
efficiently. I will also briefly mention some applications where these can be
used.