Compact Storage of Binary Trees

Abstract

Statistical measurements of the behavior of LISP programs have shown a marked asymmetry in the distribution of their data structures (binary trees).On the basis of a statistical model for such a distribution, we evaluate the expected storage cost of a representation of binary trees based on the use of k-pointer cells instead of conventional two-pointer ones.We conclude that LISP trees would be more efficiently encoded using three-pointer nodes.