On a relationship between 2-3 brother trees and dense ternary trees

Abstract

Dense multiway trees have been introduced recently. The question arises whether they can be compared to classes of balanced trees which are already known. This is the case for dense ternary trees and 2–3 brother trees. We prove that the minimal trees of the class of 2–3 brother trees and of the class of strongly dense ternary trees have the same number of leaves. We also correct an error in the original derivation of the number of keys in a minimal 2–3 brother tree.

Keywords:

• Balanced
• ternary
• 2–3
• search
• trees

C.R. Categories:

• 3.73
• 3.74
• 4.34