On the recursion depth of special tree traversal algorithms

DOI10.1016/0890-5401(87)90009-5MaRDI QIDQ579943zbMATH OpenOpenAlexFDO

Authors Peter Kirschenhofer, Helmut Prodinger

Publication date 1987

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(87)90009-5

zbMATH Keywords

analysis of algorithmsrecursive algorithmstree traversal algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Review text

In Computer Science several recursive algorithms are used for traversing the nodes of a planted plane tree. The performance of some important parameters of these algorithms may be described in terms of various notions of height. In the present paper several results on the statistics of these parameters are obtained by bijective combinatorial arguments, generating function techniques and translation lemmas for the asymptotic behaviour of the Taylor coefficients of functions having special kinds of singularities.

Recommendations

• scientific article; zbMATH DE number 3881890
• On the complexity of algorithms on recursive trees
• On the existence of special depth first search trees
• scientific article; zbMATH DE number 3854413
• A complexity calculus for recursive tree algorithms
• scientific article; zbMATH DE number 1409903
• Bounding the depth of search trees
• On the complexity of computing treelength
• On the Complexity of Computing Treelength

Cites work

• scientific article; zbMATH DE number 3134390 (Why is no real title available?)
• scientific article; zbMATH DE number 3845601 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3390782 (Why is no real title available?)
• On the number of certain lattice polygons
• q-Catalan numbers
• The average height of binary trees and other simple trees
• The average number of registers needed to evaluate a binary tree optimally
• The number of registers required for evaluating arithmetic expressions

Cited in

(9)

• FCFS-scheduling in a hard real-time environment under rush-hour conditions
• Some investigations on FCFS scheduling in hard real time applications
• Insertion depth in power-weight trees
• On the stack-size of general tries
• Computing Tree-Depth Faster Than 2 n
• scientific article; zbMATH DE number 3881890 (Why is no real title available?)
• On the existence of special depth first search trees
• Random trees in queueing systems with deadlines
• On the complexity of algorithms on recursive trees

This page was built for publication: On the recursion depth of special tree traversal algorithms

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