Added to Favorites

Related Searches

Definitions

In computer science, 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. ## External links

A natural example is the representation of a binary tree: an arbitrary binary tree on n nodes can be represented in $2n\; +\; o(n)$ 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 $n$ nodes is $\{2nchoose\; n\}/(n+1)$. For large $n$, this is about $4^n$; thus we need at least about $log\_2(4^n)=2n$ bits to encode it. A succinct binary tree therefore would occupy only $2$ bits per node.

The concept was introduced by Jacobson , to encode bit vectors, (unlabeled) trees and planar graphs in space essentially equal to the information-theoretic lower bound, while supporting navigation on it efficiently.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 19:46:39 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 19:46:39 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.