Optimal 2,3-Trees
Raymond E. Miller, Nicholas J. Pippenger, Arnold L. Rosenberg, Lawrence Snyder · SIAM Journal on Computing · 1979
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.