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

DOI10.1016/0304-3975(93)90306-EzbMATH Open0785.68044WikidataQ61734825 ScholiaQ61734825MaRDI QIDQ688684FDOQ688684

Authors: M. C. Fu 

Publication date: 6 December 1993

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Singularity Analysis of Generating Functions
• Complexity analysis of term-rewriting systems
• Title not available (Why is that?)
• A note on the height of binary search trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Altitude of Nodes in Random Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Average Size of the Intersection of Binary Trees
• Title not available (Why is that?)
• Title not available (Why is that?)

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)