Abstract
The node-visit optimal (NVO) and the space-cost optimal (SCO) height-balanced (HB) 2-3 brother trees are defined. The characterization of the NVO HB 2-3 brother trees is developed. This characterization leads to a linear-time algorithm for constructing an NVO HB 2-3 brother tree for an ordered set of keys. The minimum space-cost of an N-key NVO HB2-3 brother tree and the space-cost of an N-key SCO HB 2-3 brother tree is analysed. It is shown that the minimum space-cost of an NVO HB 2-3 brother tree is never more than one plus the space-cost of an SCO HB 2-3 brother tree. Further, the minimum node-visit cost of an SCO HB 2-3 brother tree is at most one plus the node-visit cost of an NVO HB 2-3 brother tree. It is also shown that there exists an HB 2-3 brother tree which is both SCO and NVO for just over half the possible values of keys. Finally, an outline for constructing an SCO HB 2-3 brother tree is presented.