A succinct data structure is data structure which uses an amount of space that is "close" to the information theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first.

A related notion is that of a compressed data structure, in which the size of the data structure depends upon the particular data being represented.

Succinct trees takes only “2n+O(n)” bits and support constant time computation and a set of Query operations:
•Parent(x): returns the parent of node x.
•Degree(x): returns the degree i.e. number of children of node x.
•Child(x,i): I‟th child at node x.
•Depth(x): height or distance from root x.
•LevelAncestor(x,d): return the ancestor of x with depth d.



Download attachment for a detailed presentation on Succint Trees.