The \(m\)-version of binary search trees: an average case analysis (Q1952717)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The \(m\)-version of binary search trees: an average case analysis |
scientific article; zbMATH DE number 6169804
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The \(m\)-version of binary search trees: an average case analysis |
scientific article; zbMATH DE number 6169804 |
Statements
The \(m\)-version of binary search trees: an average case analysis (English)
0 references
3 June 2013
0 references
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.
0 references
binary search trees
0 references
cost of successful search
0 references
cost of unsuccessful search
0 references
internal path length
0 references
0.8452588319778442
0 references
0.8389085531234741
0 references
