Abstract

A hierarchical data structure is provided in the form of a tree for storing key-indexed entries. Each entry of the tree includes a balance bias indicator and pointer fields for maintaining (i) link pointers to successive entries in the hierarchy or (ii) thread pointers to preceding entries in the hierarchy. Entries are added to the tree, or removed from the tree, while the tree is maintained in a height-balanced condition. During insertion of a new entry, the tree is traversed along a search path to determine an insertion point for the entry and to determine a potential rebalancing point in the tree. The potential rebalancing point in the tree is identified on the basis of the balance bias indicators of the entries in the search path. The tree is rebalanced, if necessary, about the potential rebalancing point determined during the insertion traversal.

Other References

• "Fundamentals of Data Structures in Pascal", Horowitz et al., Computer Science Press, 1990, pp. 572-591
• Brinck, Keith. The Computer Journal, "The Expected Performance of Traversal Algorithms in Binary Trees." vol. 28, No. 4, 1985, pp. 426-432
• Day, A. Colin. The Computer Journal, "Algorithms Supplement, Algorithm 91." vol. 19, No. 4, pp. 360-361
• Brinck, K. and N. Y. Foo. The Computer Journal, "Analysis of Algorithms on Threaded Trees." vol. 24, No. 2, 1981. pp. 148-155
• Zheng, Si-Qing. Proc. of the First Great Lakes Computer Science Conference, "A Simple and Powerful Representation of Binary Search Trees." 1990
• Knuth, Donald E. The Art of Computer Programming, 2nd ed., vol. 1, (Addison-Wesley: Reading, MA), 1973, pp. 314-328
• Knuth, Donald E. The Art of Computer Programming, 2nd ed., vol. 3, (Addison-Wesley: Reading, MA), 1973, pp. 423-479
• Iyengar, S. Sitharama and Hsi Chang. Software--Practice and Experience, "Efficient Algorithms to Create and Maintain Balanced and Threaded Binary Search Trees." vol. 15(10), (John Wiley & Sons, Ltd.: Oct. 1985), pp. 925-941
• Janicki, Ryszard and Waldemar W. Koczkodaj (eds.). ICCI '89, Computing and Information, vol. II, "Threaded Binary Search Trees Without Tags" by Ying Cheng. (Canadian Scholars' Press Inc.: Princeton), 1989, pp. 82-86
• Janicki, R. and W. W. Koczkodaj (eds.). Computing and Information. "Optimal Algorithms for Perfectly Balancing Trees," by Si-Qing Zheng and Enamul Haq. (Elsevier Science Publishers B.V.: North-Holland), 1989, pp. 125-129
• Akl, Selim et al. (eds.) ICCI '90, Advances in Computing and Information. "Ordered Labeling of Trees with Applications" by Ying Cheng and Si-Qing Zheng. (Canadian Scholars' Press Inc.: Toronto), 1990, pp. 19-20
• Haq, Enamul and Si-Qing Zheng. Phoenix Conference on Computers and Communications, 1989 Conference Proceedings, "Parallel Algorithms For Balancing Threaded Binary Search Trees." Mar. 22-24, 1989, pp. 286-290
• Currie, Douglas H., Jr. Fourth Dimensions, vol. II, No. 4, "Balanced Tree Deletion in FASL." pp. 96-10