Additive weights of a special class of nonuniformly distributed backtrack trees. (English) Zbl 0780.68068

Summary: We introduce a family of backtrack trees which is a generalization of a special class of the binary backtrack trees defined by P. W. Purdom. In our family each internal node may have an arbitrary degree from a finite set \(D\subset N\) of allowed node degrees. We shall assign numbers \(p_ i\in (0,1)\), \(i\in D\), to each node degree and, based on these numbers, recursively define a function which assigns a probability to each backtrack tree in our family. Next we consider a general additive weight on our family of backtrack trees and derive a general approach to the computation of the average weight of a backtrack tree of height less than or equal to \(h\) for weight functions which are polynomials of degree less than or equal to 2 in the number of leaves and the total number of nodes with coefficients depending on the degree of the root of the tree. Finally we shall apply the results presented here to some tree parameters which are important for the average case analysis of algorithms.


68Q25 Analysis of algorithms and problem complexity
68P05 Data structures
Full Text: DOI


[1] Abramowitz, M.; Stegun, I.A., Handbook of mathematical functions, (1970), Dover, New York · Zbl 0515.33001
[2] Comtet, L., Advances combinatorics, (1974), Reidel Dordrecht
[3] Kemp, R., The analysis of an additive weight of random trees, J. inform. process. cybernet, 23, 517-528, (1989) · Zbl 0641.68095
[4] Kemp, R., The expected additive weight of trees, Acta inform., 26, 7-740, (1989) · Zbl 0685.68023
[5] Kemp, R., Further results on leftist trees, (), 103-130 · Zbl 0742.05030
[6] Kemp, R., The analysis of a special class of backtrack trees, (1991), in preparation
[7] Meir, A.; Moon, J.W., On the altitude of nodes in random trees, Canad. J. math., 30, 997-1015, (1978) · Zbl 0394.05015
[8] Purdom, P.W., Tree size by partial backtracking, SIAM J. comput., 7, 481-491, (1978) · Zbl 0386.68044
[9] Trier, U., Additive gewichte bei s-nären leftist-Bäumen, Diplomarbeit, (1987), Fachbereich Informatik, Universität Frankfurt
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.