On the average internal path length of m-ary search trees (Q1060015)

Consider an m-ary tree constructed from a random permutation of size n. When all permutations are equally likely, the average internal path length, which may be considered as a cost measure for searching the tree, is shown to be \((n+1)H_ n/(H_ m-1)+cn+O(n^{\beta})\), \(\beta <1\), with \(c=c(m)=-m/(m-1)-(H_ m-1)^{-1}+A_ 1^{(m)}\), where \(H_ k\) is the \(k^{th}\) harmonic number and \(A_ 1^{(m)}\) is a coefficient obtained by solving a linear system of equations. This result tells us that the average cost of searching unbalanced m-ary trees is essentially the same as that of searching other popular variants of m-ary trees like B-trees and \(B^+\)-trees where sophisticated methods are used for balancing.