On the average number of registers needed to evaluate a special class of backtrack trees. (English) Zbl 0809.68104

Summary: We derive a lower bound for the average number of registers \(\underline {R}_ p (h)\) needed to evaluate the family \({\mathcal F}_ p (h)\) of nonuniformly distributed binary trees introduced by P. W. Purdom. This family consists of binary trees of height less than or equal to \(h\). Based on a parameter \(p \in [0,1]\), the probability of a particular tree \(T \in {\mathcal F}_ p (h)\) is given by a recursively defined function. We show that \(\underline {R}_ p (h)\) is smaller than 2, for \(0 \leq p \leq 1/2\), and that, for \(1/2 < p < 1\), it grows up to at least \(O (\log(h))\). Near \(p=1\), \(\underline {R}_ p (h)\) jumps to \(h+1\).


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity


binary trees
Full Text: DOI EuDML


[1] 1. Ph. FLAJOLET, J.-C. RAOULT and J. VUILLEMIN, The Number of Registers Required to Evaluate Arithmetic Expressions, Theoret. Comp. Sci. 1979, 9, pp. 99-125. Zbl0407.68057 MR535127 · Zbl 0407.68057
[2] 2. R. L. GRAHAM, D. E. KNUTH and O. PATASHNIK, ConcreteMathematics, Addison-Wesley, Reading, Mass. 1988. Zbl0668.00003 · Zbl 0668.00003
[3] 3. R. KEMP, The Average Number of Registers Needed to Evaluate a Binary Tree Optimally, Acta Inf., 1979, 11, pp. 363-372. Zbl0395.68059 MR533482 · Zbl 0395.68059
[4] 4. R. KEMP, The Expected Additive Weight of Trees, Acta Inf., 1989, 26, pp. 7-740. Zbl0685.68023 MR1021787 · Zbl 0685.68023
[5] 5. R. KEMP, The Analysis of a Special Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991.
[6] 6. R. KEMP, On the Stacksize of a Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991.
[7] 7. D. E. KNUTH, The Art of Computer Programming, Vol. 1, (2nd éd.), Addison-Wesley, Reading, Mass., 1973. MR378456 · Zbl 0191.17903
[8] 8. A. MEIR and J. W. MOON, On the Altitude of Nodes in Random Trees, Can. J. Math., 1978, 30 pp. 997-1015. Zbl0394.05015 MR506256 · Zbl 0394.05015
[9] 9. H. PRODINGER, Détermination de certains paramètres d’arbres binaires à l’aide de méthodes analytiques, Laboratoire de Recherche en Informatique, Université Paris 11, 91405 Orsay cedex-France, Rapport de Recherche N^\circ 177, 1984.
[10] 10. P. W. PURDOM, Tree Size by Partial Backtracking, SIAM J. Comput., 1978, 7 (4) pp. 481-491. Zbl0386.68044 MR508608 · Zbl 0386.68044
[11] 11. U. TRIER, Additive Weights of a Special Class of Nonuniformly Distributed Backtrack Trees, Inform. Proc. Letters, 1992, 42, pp. 67-76. Zbl0780.68068 MR1170871 · Zbl 0780.68068
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.