A linear algorithm for copying binary trees using bounded workspace

ABSTRACT

An algorithm to copy a binary tree in linear time using bounded workspace is presented. The algorithm does not modify the original tree at any time. The copy is constructed in such a way that it can be traversed in a read-only fashion even before the copying process is complete, provided one can distinguish between the original and the copy. The traversal can be carried out in parallel with the copying.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Clark, D.W. A fast algorithm for copying binary trees, lnform. Processing Letters 4 (1975), 62-63.
• 3: Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978 [doi>10.1145/359488.359491]
• 4: David A. Fisher, Copying cyclic list structures in linear time using bounded workspace, Communications of the ACM, v.18 n.5, p.251-252, May 1975 [doi>10.1145/360762.360764]
• 5: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 6: Horowitz, E., and Sahni, S. Fundamentals of Data Structures. Comptr. Sci. Press, Woodland Hills, Calif., 1976.
• 7: Lindstrom, G. Scanning list structures without stacks or tag bits. Inform. Processing Letters 2 (1973), 47~51.
• 8: Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974 [doi>10.1145/360924.360936]
• 9: J. M. Robson, A bounded storage algorithm for copying cyclic structures, Communications of the ACM, v.20 n.6, p.431-433, June 1977 [doi>10.1145/359605.359628]
• 10: Wang, C.C. A linear algorithm for copying binary trees using bounded workspace. Tech. Rep. No. 43-78, Dept. of Comptr. Sci., Univ. of Kentucky.

INDEX TERMS

Keywords:
binary trees, copying, tree traversal