Average-case analysis on simple families of trees using a balanced probability model

DOI10.1016/0304-3975(93)90306-EMaRDI QIDQ688684zbMATHWikidataFDO

Authors M. C. Fu

Publication date 6 December 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

occupancyintersectionuniform modelbinary search treebalanced model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Additive weights under the balanced probability model
• Binary search trees constructed from nondistinct keys with/without specified probabilities
• Average-case analysis of pattern-matching in trees under the BST probability model
• Analysis of the space of search trees under the random insertion algorithm
• The \(m\)-version of binary search trees: an average case analysis

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 176734 (Why is no real title available?)
• scientific article; zbMATH DE number 3468275 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3482771 (Why is no real title available?)
• scientific article; zbMATH DE number 3587312 (Why is no real title available?)
• scientific article; zbMATH DE number 1142298 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A note on the height of binary search trees
• Complexity analysis of term-rewriting systems
• On the Altitude of Nodes in Random Trees
• On the Average Size of the Intersection of Binary Trees
• Singularity Analysis of Generating Functions

Cited in

(2)

• Average case analysis for tree labelling schemes
• The effects of semantic simplifications on random \textit{BST}-like expression-trees

This page was built for publication: Average-case analysis on simple families of trees using a balanced probability model

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