All Topics  
Succinct data structure

 

 
   Email Print
   Bookmark   Link
 

 

Succinct data structure
 
 
  Topics Succinct data structure Topic Home

In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, a succinct data structure for a given data type is a representation of the underlying combinatorial object that uses an amount of space “close” to the information theoretic lower bound together with efficient algorithms for navigation, search, insertion and deletion operations.

A natural example is the representation of a binary tree
Binary tree

In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right....
: an arbitrary binary tree on n nodes can be represented in bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time.






Discussion
Ask a question about 'Succinct data structure'
Start a new discussion about 'Succinct data structure'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, a succinct data structure for a given data type is a representation of the underlying combinatorial object that uses an amount of space “close” to the information theoretic lower bound together with efficient algorithms for navigation, search, insertion and deletion operations.

A natural example is the representation of a binary tree
Binary tree

In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right....
: an arbitrary binary tree on n nodes can be represented in bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time. The number of different binary trees on nodes is . For large , this is about ; thus we need at least about bits to encode it. A succinct binary tree therefore would occupy only bits per node.

The concept was introduced by Jacobson , to encode bit vectors, (unlabeled) trees and planar graph
Planar graph

In graph theory, a planar graph is a graph which can be graph embedding in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints....
s in space essentially equal to the information-theoretic lower bound, while supporting navigation on it efficiently.

External links