Destruction of recursive trees

From MaRDI portal





If a randomly chosen edge is removed from one of the \((n- 1)!\) recursive trees \(T\) with \(n\) labelled vertices, then \(T\) falls into two subtrees one of which contains the root vertex with label 1. Suppose we continue to remove edges from the successively smaller subtrees that contain the root. \textit{A. Meir} and \textit{J. W. Moon} [Math. Biosci. 21, 173--181 (1974; Zbl 0288.05102)] determined the expected number of edges that are removed before the root is isolated and the process stops. The author of the present paper introduces a cost \(c_m= m^\alpha\), \(\alpha\geq 0\), associated with removing an edge from a recursive tree with \(m\) vertices. He considers the procedure just described and a related procedure in which the edge-removing process is applied to all subtrees encountered and terminates when all edges have been removed. He determines the asymptotic behaviour of the \(s\)th moment and the \(s\)th centered moment of the total costs incurred before these two processes terminate, for any fixed positive integer \(s\). In particular, the expected value of the total cost for both procedures is asymptotic to \(n^{\alpha+ 1}/(\alpha+ 1)\log n\), where we assume that \(\alpha> 0\) in the case of the second procedure. For the entire collection see [Zbl 1047.68003].











This page was built for publication: Destruction of recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3154689)