The week's pick
Random Articles
Reseach Article
The Binary Tree Roll Operation: Definition, Explanation and Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 46 - Number 8 |
| Year of Publication: 2012 |
| Authors: Adrijan Božinovski, Nevena Ackovska |
10.5120/6931-9425
|
Adrijan Božinovski, Nevena Ackovska . The Binary Tree Roll Operation: Definition, Explanation and Algorithm. International Journal of Computer Applications. 46, 8 ( May 2012), 40-47. DOI=10.5120/6931-9425
Abstract
The paper introduces an operation on a binary tree, called binary tree roll, or roll of a binary tree. Two versions of the binary tree roll, counterclockwise and clockwise, are presented. The operations are mathematically defined and graphically presented. It is explained how the binary tree roll actually coincides with the process of turning the entire tree 90 degrees counterclockwise or clockwise. To visually explain and perform the roll operation, the concepts of a wedge node, true ancestor, illusory ancestor, illusory root and illusory ancestral stem of nodes are introduced, as well as the visual operations of turning and downshift. Both roll operations are implemented using programming algorithms. The algorithms are explained, and all the situations that might be encountered during processing the roll operation are examined and resolved. Thus, the paper gives a mathematical introduction of both binary tree roll operations, gives their visual explanations and offers algorithms for their implementations using a computer.
References
- Sedgewick, R. 1998. Algorithms in C++, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley.
- Brassard, G. and Bratley, P. 2002. Fundamentals of Algorithmics. Prentice Hall of India
- Bozinovski, A. and Bozinovski, S. 2004. N-queens pattern generation: An insight into space complexity of a backtracking algorithm. In Proceedings of the 3rd International Symposium on Information and Communication Technologies. Las Vegas, Nevada, USA, 281-286
- Sedgewick, R. 2002. Algorithms in C++, Part 5: Graph Algorithms. Pearson
- Freedman, R. Binary Tree Operations. Notes on CS340: Data Structures and Algorithm Analysis. Department of Computer Science, Northern Illinois University. http://faculty. cs. niu. edu/~freedman/340/340notes/340btreeop. htm. Accessed 10 January 2012
- Mostafa, H. 2005. Fast Binary Tree Operations. The Code Project. http://www. codeproject. com/KB/recipes/BinaryTree. aspx. Accessed 10 January 2012
- Kruse, G. W. 2007. Binary Tree Operations. CS240: Computer Science II. Department of Information Technology and Computer Science. Juniata College. http://jcsites. juniata. edu/faculty/kruse/cs240/bintree. htm. Accessed 10 January 2012
- Sleator, D. D. , Tarjan, R. E. , and Thurston, W. P. 1988. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society. Vol 1. No 3. 647-681
- Chen, W. Y. C. and Yang, L. L. M. 2008. On Postnikov's hook length formula for binary trees. European Journal of Combinatorics. Doi: 10. 1016/j. ejc. 2007. 11. 025
- Doshi, N. , Sureja, T. , Akbari, B. , Savaliya, H. , and Daxini, V. 2010. Width of a Binary Tree. International Journal of Computer Applications. Vol 9. No 2. 41-43
- Arora, N. , Tamta, V. K. , and Kumar, S. 2012. Modified Non-Recursive Algorithm for Reconstructing a Binary Tree. International Journal of Computer Applications. Vol 43. No 10. 25-28
- Zhou, A. , Huang, S. , and Wang, X. 2007. BITS: A Binary Tree Based Web Service Composition System. International Journal of Web Services Research. Vol 4. No 1. 40-58
- Duarte, E. P. Jr, Pires, K. , and Tavares, R. A. E. 2010. An efficient strategy for storing and searching binary trees in WORM external memory. Journal of Information Science. Vol 36. No 6. 751-762
- Wang, D. , Zheng, J. , and Zhou, Y. 2011. Binary tree of posterior probability support vector machines. Journal of Zhejiang University – Science C. Vol 12. No 2. 83-87
- Burgdorff, H. A. , Jajodia, S. , Springsteel, F. N. , and Zalcstein, Y. 1987. Alternative methods for the reconstruction of trees from their traversals. BIT Numerical Mathematics. Vol 27. No 2. 133-140
- Narahari, Y. 4. 2 Binary Trees. Data Structures and Algorithms. Computer Science and Automation. Indian Institute of Science. http://lcm. csa. iisc. ernet. in/dsa/node87. html. Accessed 10 January 2012
- Božinovski, A. 2011. Linear-Time Binary Tree Generation Algorithms for Arbitrary Input String Reproduction upon Depth-First Traversal and Rotation of a Binary Tree. International Conference on Innovative Technologies IN-TECH. Bratislava, Slovakia. 58-61
Index Terms
Keywords