Dense multiway trees

ABSTRACT

B-trees of order m are a “balanced” class of m-ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced m-ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order m. Surprisingly, we are able to demonstrate that weakly dense multiway trees have an &Ogr;(log2 N) insertion algorithm. We also show that inserting mh - 1 keys in ascending order into an initially empty dense multiway tree yields the complete m-ary tree of height h, and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense m-ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”

REFERENCES

• 1: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. 1 (1972), 173-189.
• 2: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 3: KRIEGEL, H.P., VAISHNAVl, V.K., AND WOOD, D. 2-3 brother trees. BIT 18 (1978), 425-435.
• 4: LARSON, J.A., AND WALDEN, W.E. Comparing insertion schemes used to update 3-2 trees. Tech. Rep., Univ. New Mexico, Albuquerque, N. Mex., 1979.
• 5: LIu, C.L. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, 1968.
• 6: MEHLHORN, K. Private communication, 1979.
• 7: OLIVIa, H.J. On the relationship between 2-3 brother trees and dense ternary trees, int. J. Comput. Math. 8A (A80), 233-245.
• 8: OTTMANN, TH., AND SIX, H.W. Eine neue Klasse von ausgeglichenen Bin~b~iumen. Angew. Inf. 18, 9 (1976), 395-400.
• 9: OTTMANN, TH., AND STUCKY, W. Higher order analysis of random 1-2 brother trees. BIT 20 (1980), 302-314.
• 10: OTTMANN, TH., AND WOOD, D. 1-2 brother trees or AVL trees revisited. Comput. J. 23 {1980), 248-255.
• 11: OTTMANN, T~., AND WOOD, D. A uniform approach to balanced binary and multiway trees. Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science, vol. 74, Springer-Verlag, New York, 1979, pp. 398-407.
• 12: PAVZAK, E. Dichte 3-Weg Biiume, Master's thesis, Karlsruhe, I978.
• 13: ROSENBERG, A.L., AND SNYDER, L. Minimal comparison 2, 3 trees. SIAM J. Comput. 7 (1978), 465-480.
• 14: ROS~NB~aG, A.L., AND SNYDER, L. Compact B-trees. Rep. RC 7343, IBM T.J. Watson Research Center, Yorktown Heights, N.Y.
• 15: YAO, A. On random 2, 3, trees. Acta Inf. 9 (1978}, 159-170.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Algorithms, Design

Keywords:
B-trees, balanced trees, dense trees, multiway trees, search trees, storage utilization