Minimal-Comparison $2,3$-Trees

Those 2,3-trees that are minimal in expected number of comparisons per access for a given number of keys are characterized. The characterization yields directly a linear-time algorithm for constructing a minimal-comparison 2,3-tree for a given sorted set of keys. Regrettably, the property of comparison minimality is incompatible with the earlier-studied property of node-visit optimality. Specifically, the two types of optimality can coexist in a K-key 2,3-tree only for sixteen values of K, none exceeding 32. In contrast, comparison-minimal node-visit-pessimalK-key 2,3-trees exist for just over half the possible values of K.