Document Type
Article
Department
Mathematics (HMC)
Publication Date
1979
Abstract
The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.
Rights Information
© 1979 Society for Industrial and Applied Mathematics
Recommended Citation
Miller, Raymond E., Nicholas Pippenger, Arnold L. Rosenberg, and Lawrence Snyder. “Optimal 2,3-Trees*.” SIAM Journal on Computing 8, no. 1 (February 1979): 42-59.
COinS
