Expected Costs in Some Classes of Binary Search Trees

DOI10.1080/02522667.1984.10698792MaRDI QIDQ3219127zbMATH OpenOpenAlexFDO

Authors Hajime Fukushima

Publication date 1984

Published in Journal of Information and Optimization Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02522667.1984.10698792

zbMATH Keywords

average path lengthsbinary search treesexpected costrandom trees

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Binary search trees with binary comparison cost
• Optimum lopsided binary trees
• Randomized binary search trees
• scientific article; zbMATH DE number 3909754
• Optimal binary search trees with costs depending on the access paths.

Cites work

• Heuristics That Dynamically Organize Data Structures
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Self-Organizing Binary Search Trees
• Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting

Cited in

(18)

• The node visit cost of brother trees
• Binary search trees constructed from nondistinct keys with/without specified probabilities
• New lower bounds on the cost of binary search trees
• Optimal binary search trees with costs depending on the access paths.
• Emerging behavior as binary search trees are symmetrically updated.
• The m-version of binary search trees: an average case analysis
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• scientific article; zbMATH DE number 1629950 (Why is no real title available?)
• Cost allocation in asymmetric trees
• Binary search trees with binary comparison cost
• Cost-error relationships in A* tree-searching
• The Expected Performance of Traversal Algorithms in Binary Trees
• scientific article; zbMATH DE number 3909754 (Why is no real title available?)
• Expected conflicts in pairs of rooted binary trees
• Optimum lopsided binary trees
• (Un)expected path lengths of asymmetric binary search trees
• scientific article; zbMATH DE number 5046289 (Why is no real title available?)
• Average number of rotations access cost in iR-trees

This page was built for publication: Expected Costs in Some Classes of Binary Search Trees

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