Abstract

We propose to maintain a Binary Search Tree in the form of a forest in such a way that – (a) it provides faster node access and, (b) it becomes more compatible with the concurrent environment. Using a small array, the stated goals were achieved without applying any restructuring algorithm. Empirically, we have shown that the proposed method brings down the total internal path-length of a Binary Search Tree quite considerably. The experiments were conducted by creating two different data structures using the same input - a conventional binary search tree, and a forest of hashed trees. Our empirical results suggest that the forest so produced has lesser internal path length and height in comparison to the conventional tree. A binary search tree is not a well-suited data structure for concurrent processing. The evidence also shows that maintaining a large tree in form of multiple smaller trees (forest) increases the degree of parallelism.

References

• Adel’son-Vel’skii, G. M, and Landis E. M, 1962. “An Algorithm for the Organization of Information, Soviet Mathematics Doklady”, Vol. 3, 1259–1263.
• Martin, W. A, and Ness, D. N. 1972, “Optimal Binary Trees Grown with a Sorting Algorithm”, Communication. of the ACM, 15, 88-93.
• Bayer, R. 1972, “Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms”, Acta Informatica. 1, 290–306.
• Day, A. C. 1976, “Balancing a Binary Tree, Computer Journal”, 19, 360-361.
• Samadi, B. 1976, “B Trees in System with Multiple Users”, Information Processing Letters, 5 (4), 107-112.
• Eswaran, K. P., Gray, J. N., Lorie, R. A, and Traiger, I. L. 1976, “The notions of Consistency and Predicate Locks in a Database System”, Communication of the ACM, 19(11), 624-633.
• Bayer, R., Schkolnick, M. 1977, “Concurrency of Operations on B Trees”, Acta Informatica, 9(1), 1-21, 1977
• Ries, D. R., Stonebreaker, M. 1977, “Effects of Locking Granuality in a Database Management System”. ACM Trans. Database Systems, 2(3) , 233-246, 1977
• Ellis, C. S. 1980. “Concurrent search and insertion in AVL trees”. IEEE Transactions on Computers, Vol 29, 811–817.
• Ellis, C. S. 1980, “Concurrent search and insertion in 2-3 trees”. Acta Informatica, Vol 14, 63–86, 1980
• 11 Kung, H. T., Lehman, P. L. 1980, “Concurrent manipulation of binary search trees”. ACM Transactions on Database Systems, Vol. 5, 354–382
• 12 Eppinger, J. L. 1983, “An Empirical Study of Insertion and Deletion in Binary Search Trees”, Communication of the ACM, 26, 663-669.
• 13 Gonnet, G. H. 1983, “Balancing binary Search Trees by Internal Path Reduction”, Communication of the ACM, 26(12), 1074-1081.
• 14 Chang, H, Iyengar, S. S, 1984, “Efficient Algorithms To Globally Balance a Binary Search Tree”, Communication of the ACM, 27, 695-702.
• 15 Sleator, D. D., Tarjon, R. E, 1985, “Self-Adjusting Binary Search Trees”. Journal of The ACM, 32(3), 652-686.
• 16 Stout, F, Bette, L. W. 1986, “Tree Rebalancing in Optimal Time and Space”, Communication of the ACM, 29, 902-908.
• 17 Gerasch, T. E. 1988, “An insertion algorithm for a minimal internal path length binary search tree”. Communications of the ACM, Vol.31 (5), 579–585.
• 18 Bell, J., Gupta, G. 1993, “An evaluation of self-adjusting binary search tree techniques”. Software Practice and Experience, Vol. 23(4), 369–382.
• 19 Knuth, D. E. 2005, The Art of Computer Programming,” Pearson Education, Vol. 3, Searching and Sorting.