We consider the implementation of abstract data types for thestatic objects: binary tree, rooted ordered tree and balancedparenthesis expression. Our representations use an amount of spacewithin a lower order term of the information theoretic minimum andsupport, in constant time, a richer set of navigational operations thanhas previously been considered in similar work. In the case of binarytrees, for instance, we can move from a node to its left or right childor to the parent in constant time while retaining knowledge of the sizeof the subtree at which we are positioned. The approach is applied toproduce succinct representation of planar graphs in which one can testadjacency in constant time
展开▼
