The \(m\)-version of binary search trees: an average case analysis (Q1952717)

Summary: Following a suggestion of \textit{J. Cichoń} and \textit{W. Macyna} [``Approximate counters for flash memory'', in Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'11), Toyama, Japan (2011)], 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.