Time- and Space-optimal height-balanced 2-3 brother trees

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.

Keywords:

• 2-3 trees
• B-trees
• height-balanced 2-3 trees
• comparisons per access
• 2-3 brother trees

C.R. Categories::

• 3.73
• 3.74
• 4.34