Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Mathematics
Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder
Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder
All HMC Faculty Publications and Research
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.