scientific article; zbMATH DE number 437541

MaRDI QIDQ3140418zbMATH OpenFDO

Authors Igal Galperin, Ronald L. Rivest

Publication date 15 December 1993

zbMATH Keywords

binary search treesscapegoat tree

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Deletion without rebalancing in binary search trees
• Self-adjusting binary search trees
• Balancing binary trees by internal path reduction
• Deletion without rebalancing in balanced binary trees
• Binary search trees of almost optimal height

Cited in

(13)

• Randomized search trees
• Dynamic hotlinks
• Rank-Sensitive Priority Queues
• Efficient and robust path openings using the scale-invariant rank operator
• Polylogarithmic fully retroactive priority queues via hierarchical checkpointing
• Verified Root-Balanced Trees
• Balanced search trees made simple
• Nearly optimal separation between partially and fully retroactive data structures
• Supernode Binary Search Trees
• Monotone meshfree methods for linear elliptic equations in non-divergence form via nonlocal relaxation
• Bottom-up rebalancing binary search trees by flipping a coin
• Online list labeling: breaking the ^2n barrier
• Upper and lower bounds for fully retroactive graph problems

This page was built for publication:

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