آنالیز حاشیه ای درختان مسطح مرتبط با برش و هرس کردن Fringe analysis of plane trees related to cutting and pruning

1. Introduction Plane trees are among the most interesting elementary combinatorial objects; they appear in the literature under many different names such as ordered trees, planar trees, planted plane trees, etc. They have been analyzed from various aspects, especially due to their relevance in Computer Science. Two particularly well-known quantities are the height, since it is equivalent to the stack size needed to explore binary (expression) trees, and the pruning number (pruning index), since it is equivalent to the register function (Horton–Strahler number) of binary trees. Several results for the height of plane trees can be found in [3,7,22], for the register function, we refer to [4,9,17], and for results on the connection between the register function and the pruning number to [4,27]. Reducing (cutting-down) trees has also been a popular research theme during the last decades [15,19,21]: according to a certain probabilistic model, a given tree is reduced until a certain condition is satisfied (usually, the root is isolated). In the present paper, the point of view is slightly different, as we reduce a tree in a completely deterministic fashion at the leaves until the tree has no more edges. All these reductions take place on the fringe, meaning that only (a subset of) leaves (and some adjacent structures) are removed. We consider four different models: – In one round, all leaves together with the corresponding edges are removed (see Sect. 2). – In one round, all maximal paths (linear graphs), with the leaves on one end, are removed (see Sect. 3). This process is called pruning. – A leaf is called an old leaf if it is the leftmost sibling of its parents. This concept was introduced in [2]. In one round, only old leaves are removed (see Sect. 4). – The last model deals with pruning old paths. There might be several interesting models related to this; the one we have chosen here is that in one round maximal paths are removed, under the condition that each of their nodes is the leftmost child of their parent node (see Sect. 5). The four tree reductions are illustrated in Fig. 1. We describe these reductions more formally in the corresponding sections. The first model is clearly related to the height of the plane tree, and the second one to the Horton–Strahler number via the pruning index [24,27]. While there are no surprises about the number of rounds that the process takes here, we are interested in how the fringe develops. The number of leaves and nodes altogether in the remaining tree after a fixed number of reduction rounds is the main parameter analyzed in this paper.