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.
No takes yet. Share an insight, caveat, or question.
Miller et al. (1979) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: