A new data structure for representing sorted lists

DOI10.1007/BF00288968zbMath0481.68061OpenAlexW2077180154MaRDI QIDQ1162362

Scott Huddleston, Kurt Mehlhorn

Publication date: 1982

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288968

zbMATH Keywords

balanced treesweak B-treesworst case cost of sequences of insertions and deletions

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

I/O-efficient dynamic planar point location, A constant update time finger search tree, Predecessor queries in dynamic integer sets, Visibility between two edges of a simple polygon, The buffer tree: A new technique for optimal I/O-algorithms, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Amortized Computational Complexity, A balanced search tree O(1) worst-case update time, An optimal visibility graph algorithm for triangulated simple polygons, Making data structures persistent, Amortization results for chromatic search trees, with an application to priority queues, Deletion without rebalancing in multiway search trees, Red-black trees with constant update time, Relaxed multi-way trees with group updates., Fully persistent B-trees, Dynamic fractional cascading, Unnamed Item, Towards a real time algorithm for parameterized longest common prefix computation, I/O-efficient algorithms for computing planar geometric spanners, Dynamic Planar Range Maxima Queries, A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, AVL trees with relaxed balance, Improved output-sensitive snap rounding, Computing the external geodesic diameter of a simple polygon, Amortization results for chromatic search trees, with an application to priority queues, Optimal finger search trees in the pointer machine, Dynamic interpolation search revisited, Unnamed Item, I/O-efficient point location using persistent B-trees, External memory planar point location with logarithmic updates, Multi-Finger Binary Search Trees, Some Results for Elementary Operations, Updating a balanced search tree in 0(1) rotations, VARIANTS OF (A,B)-TREES WITH RELAXED BALANCE, Maintaining order in a generalized linked list, Optimal multiway search trees for variable size keys, Exponentially decreasing number of operations in balanced trees, On the existence and construction of non-extreme \((a,b)\)-trees., Unnamed Item, A workbench for computational geometry

Cites Work

• Unnamed Item
• On the average number of rebalancing operations in weight-balanced trees
• Organization and maintenance of large ordered indexes
• Symmetric binary B-trees: Data structure and maintenance algorithms
• Design and Analysis of a Data Structure for Representing Sorted Lists