Destruction of Recursive Trees
Alois Panholzer · Birkhäuser Basel eBooks · 2004
We study for the family of recursive trees, two procedures that destroy trees by successively removing edges. In both variants, one starts with a tree T of size n and chooses one of the n —1 edges at random. Removing this edge costs a toll depending on the size of T , given by the toll function t n and leads to two subtrees T’ and T“. In the one-sided variant, the edge-removal procedure will be iterated with the subtree containing the root , whereas in the two-sided variant it will be iterated with both subtrees. For both variants , we study for toll functions t n = n а with а ≥ 0 the total costs (= sum of the tolls of every step) obtained by completely destroying random recursive trees , where we compute for this quantity the asymptotic behaviour of all moments . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.