Compaction for two models of logarithmic-depth trees: Analysis and Experiments
share
In this paper we are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing tree. These families are typical representatives of tree models with a small depth. More formally, asymptotically, for a random tree with n nodes, its depth is of order log n. Once a tree of size n is compacted by keeping only one occurrence of all fringe subtrees appearing in the tree the resulting graph contains only O(n / log n) nodes. This result must be compared to classical results of compaction in the families of simply generated trees, where the analog result states that the compacted structure is of size of order n / √(log n). We end the paper with an experimental quantitative study, based on a prototype implementation of compacted binary search trees, that are modeled by plane binary increasing trees.
READ FULL TEXT