论文部分内容阅读
Abstract: The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height with all leaves on the same level, and the related subtrees of height . These are called trees and subtrees. The recursive and nonrecursive versions of the traversal algorithms for the trees with dynamically created nodes are discussed. The original nonrecursive algorithms that return the pointer to the next node in preorder, inorder and postorder traversals are presented. The space-time complexity analysis shows and the execution time measurements confirm that for these algorithms, the recursive versions have approximately 10-25% better time constants. Still, the use of nonrecursive algorithms may be more appropriate in several occasions.
Key words: Binary-trees, algorithms, tree traversal, preorder, inorder, postorder, recursive, nonrecursive, space-time complexity.
1. Introduction
The choice and comparison of recursive versus nonrecursive algorithms is a known subject from the algorithm-study in computer science. It is found in the major textbooks, it is investigated by scientists, and discussed by professionals. In this paper we present the design and complexity analysis of a few testing and practical functions that do their job on dynamically created tree nodes by using both recursive and nonrecursive tree traversal algorithms.
The implementation of the algorithms and their testing is done within our DSA (Dynamical Systems Automata) program for the modeling of dynamical systems from a time series, based on J. P. Crutchfield’s theory of ?-machines [1]. In [2] we have presented the outline and some interesting aspects of the theory for the readers from the computing area. The resulting dynamical system models are based on the stochastic finite automata, which are analogous to the finite automata from the theory of computation. As such, the modeling scheme turns out to be an intriguing programming challenge from the perspective of computer science. Quite general structural and algorithmic problems were addressed during the development of the DSA modeling tool, which are interesting for their design analysis and efficiency testing. From quite a few of them, here we concentrate on the tree structures and the algorithms that traverse through, and operate on, their nodes.
References
[1] J.P. Crutchfield, Computational Mechanics Publications, available online at: http://csc.ucdavis.edu/~chaos/chaos/pub s.htm, accessed: April 2012.
[2] R. Logozar, A. Lovrencic, The modeling and complexity of dynamical systems by means of computation and information theories, Journal of Information and Organizational Sciences 35 (2) (2011).
[3] E. Horowitz, S. Sahni, Fundamentals of Computer Algorithms, Pitman Publish Ltd., London, 1979.
[4] N. Wirth, Algorithms & Data Structures (New Edition), Prentice/Hall International, London, 1986.
[5] A.B. Tucker at al., Fundamentals of Computing II, C++ Edition, McGraw-Hill, New York, 1995.
[6] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974.
[7] R. Logozar, Modeling of dynamical systems by stochastic finite automata, Master Thesis, Faculty of Electrical Engineering and Computing, University of Zagreb, 1999.
Key words: Binary-trees, algorithms, tree traversal, preorder, inorder, postorder, recursive, nonrecursive, space-time complexity.
1. Introduction
The choice and comparison of recursive versus nonrecursive algorithms is a known subject from the algorithm-study in computer science. It is found in the major textbooks, it is investigated by scientists, and discussed by professionals. In this paper we present the design and complexity analysis of a few testing and practical functions that do their job on dynamically created tree nodes by using both recursive and nonrecursive tree traversal algorithms.
The implementation of the algorithms and their testing is done within our DSA (Dynamical Systems Automata) program for the modeling of dynamical systems from a time series, based on J. P. Crutchfield’s theory of ?-machines [1]. In [2] we have presented the outline and some interesting aspects of the theory for the readers from the computing area. The resulting dynamical system models are based on the stochastic finite automata, which are analogous to the finite automata from the theory of computation. As such, the modeling scheme turns out to be an intriguing programming challenge from the perspective of computer science. Quite general structural and algorithmic problems were addressed during the development of the DSA modeling tool, which are interesting for their design analysis and efficiency testing. From quite a few of them, here we concentrate on the tree structures and the algorithms that traverse through, and operate on, their nodes.
References
[1] J.P. Crutchfield, Computational Mechanics Publications, available online at: http://csc.ucdavis.edu/~chaos/chaos/pub s.htm, accessed: April 2012.
[2] R. Logozar, A. Lovrencic, The modeling and complexity of dynamical systems by means of computation and information theories, Journal of Information and Organizational Sciences 35 (2) (2011).
[3] E. Horowitz, S. Sahni, Fundamentals of Computer Algorithms, Pitman Publish Ltd., London, 1979.
[4] N. Wirth, Algorithms & Data Structures (New Edition), Prentice/Hall International, London, 1986.
[5] A.B. Tucker at al., Fundamentals of Computing II, C++ Edition, McGraw-Hill, New York, 1995.
[6] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974.
[7] R. Logozar, Modeling of dynamical systems by stochastic finite automata, Master Thesis, Faculty of Electrical Engineering and Computing, University of Zagreb, 1999.