One-Sided Interval Trees

We give an alternative treatment and extension of some results of Itoh and Mahmoud on one-sided interval trees. The proofs are based on renewal theory, including a case with mixed multiplicative and additive renewals. 1 Introduction Itoh and Mahmoud [2] have studied some one-sided versions of binary interval trees. These are obtained from full binary interval trees (see Section 2 for definitions) by pruning one of the two subtrees at each node; in other words, we are left with a single path in the binary interval tree. Five different such trees, defined by different pruning policies, are studied in [2]. Using an analytic method, Itoh and Mahmoud find explicit or implicit expressions for the moment generating function of the size of the tree, and they derive in each case asymptotic normality and asymptotic expressions for the mean and variance of the size.We will here give an alternative treatment using renewal theory, which enables us to generalize the results. In particular, the results