The m-version of binary search trees: an average case analysis

DOI10.1155/2013/450627MaRDI QIDQ1952717zbMATH OpenOpenAlexWikidataFDO

Authors Helmut Prodinger

Publication date 3 June 2013

Published in ISRN Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2013/450627

zbMATH Keywords

binary search treescost of successful searchcost of unsuccessful searchinternal path length

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• On the average internal path length of m-ary search trees
• Some average measures in m-ary search trees
• Expected Costs in Some Classes of Binary Search Trees
• scientific article; zbMATH DE number 168426
• An analytic approach to the height of binary search trees. II

Cites work

• Analytic combinatorics
• Approximate counting: a detailed analysis
• Comparisons in Hoare's Find Algorithm
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Linear probing and graphs
• Randomized binary search technique

Cited in

(7)

• On the average internal path length of m-ary search trees
• Some average measures in m-ary search trees
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• scientific article; zbMATH DE number 1143799 (Why is no real title available?)
• scientific article; zbMATH DE number 6145140 (Why is no real title available?)
• Digital search trees with m trees: level polynomials and insertion costs
• Average-case analysis on simple families of trees using a balanced probability model

Describes a project that uses

Uses Software

• Find

This page was built for publication: The \(m\)-version of binary search trees: an average case analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1952717)