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 treesinternal path lengthcost of successful searchcost of unsuccessful search

Mathematics Subject Classification ID

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

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

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

Cited in

(7)

• On the average internal path length of 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?)
• Digital search trees with \(m\) trees: level polynomials and insertion costs
• Some average measures in m-ary search trees
• scientific article; zbMATH DE number 6145140 (Why is no real title available?)
• 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)