Succinct Representations of Trees

摘要

Trees are by far the most common data structures to represent/organize/search large amount of data. Part of the trees' success is probably due to the simplicity of the usual pointer-based implementation in which to move from parent to child we simply follow a pointer. Unfortunately, a simple counting argument shows that the pointer-based implementation is highly redundant. The number of distinct trees with n nodes is given by the n-th Catalan number.