The m-Version of Binary Search Trees: An Average Case Analysis. (19th December 2012) - Prodinger, Helmut
Abstract : Following a suggestion of Cichoń and Macyna, binary search trees are generalized by keeping m (classical) binary search trees and distributing incoming data at random to the individual trees. Costs for unsuccessful and successful search are analyzed, as well as the internal path length.