Self-adjusting binary search trees
From MaRDI portal
Publication:3768416
DOI10.1145/3828.3835zbMath0631.68060OpenAlexW2130055503WikidataQ30053257 ScholiaQ30053257MaRDI QIDQ3768416
Daniel Dominic Sleator, Robert Endre Tarjan
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3828.3835
amortized complexitynetwork optimizationbalanced treesself-adjustmentself-organizing data structuresmultidimensional searching
Related Items
Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components, Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing, The Parametric Closure Problem, Self-Adjusting Binary Search Trees: What Makes Them Tick?, Randomized online multi-threaded paging, Serving requests with on-line routing, Tables should be sorted (on random access machines), Fast algorithms for one-dimensionsal compaction with jog insertion, A Distribution-Sensitive Dictionary with Low Space Overhead, Rank-Sensitive Priority Queues, Skip-Splay: Toward Achieving the Unified Bound in the BST Model, Adaptive Point Location in Planar Convex Subdivisions, An efficient algorithm for estimating rotation distance between two binary trees, Amortized Computational Complexity, Splay trees as priority queues, The inverse Voronoi problem in graphs. II: Trees, Amortized Complexity Verified, On stable flows and preflows, The splay-list: a distribution-adaptive concurrent skip-list, Maximum skew-symmetric flows, Effective splaying with restricted rotations, A Linear Potential Function for Pairing Heaps, Unnamed Item, Determinant-Preserving Sparsification of SDDM Matrices, Unnamed Item, Optimal purely functional priority queues, Unnamed Item, Smooth Heaps and a Dual View of Self-Adjusting Data Structures, The move-to-root rule for self-organizing trees with Markov dependent requests∗, Supernode Binary Search Trees, Local properties of geometric graphs, Pairing heaps: the forward variant., A consistent semantics of self-adjusting computation, Dynamic Trees with Almost-Optimal Access Cost, Self‐adjusting trees in practice for large text collections, Simple and Efficient Clause Subsumption with Feature Vector Indexing, Unnamed Item, A note on the parametric maximum flow problem and some related reoptimization issues, Adaptive sorting: an information theoretic perspective, The cost of offline binary search tree algorithms and the complexity of the request sequence, A simpler and faster 1.5-approximation algorithm for sorting by transpositions, Optimal binary search trees, Randomized algorithms for metrical task systems, Critical sizing of LRU caches with dependent requests, The Generalized Stable Allocation Problem, Incremental Computing with Abstract Data Structures, Near-entropy hotlink assignments, Belga B-trees, THE VIOLATION HEAP: A RELAXED FIBONACCI-LIKE HEAP, Automatic Functional Correctness Proofs for Functional Search Trees, Rotation Distance, Triangulations, and Hyperbolic Geometry, Online Learning over a Finite Action Set with Limited Switching, A History of Distribution-Sensitive Data Structures, A Survey on Priority Queues, In Pursuit of the Dynamic Optimality Conjecture, Succinct Representations of Ordinal Trees, Efficient algorithms for online decision problems, A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY, Adaptive Planar Point Location, Self-adjusting Grid Networks to Minimize Expected Path Length, Competitive Online Search Trees on Trees, Type-based analysis of logarithmic amortised complexity, On list update with locality of reference, The list update problem and the retrieval of sets, A multi-stage hierarchical clustering algorithm based on centroid of tree and cut edge constraint, ATLAS: automated amortised complexity analysis of self-adjusting data structures, On minimum generalized Manhattan connections, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, The pairing heap: A new form of self-adjusting heap, Improving time bounds on maximum generalised flow computations by contracting the network, Linear-time construction of treaps and Cartesian trees, Categorified Reeb graphs, Large alphabets and incompressibility, Approximate regular expression pattern matching with concave gap penalties, Computing on a free tree via complexity-preserving mappings, A unified access bound on comparison-based dynamic dictionaries, A faster algorithm for computing the principal sequence of partitions of a graph, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, On top-down splaying, Efficient and robust path openings using the scale-invariant rank operator, On bicriterion minimal spanning trees: An approximation, A direct algorithm for restricted rotation distance, A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph, On the hierarchy of distribution-sensitive properties for data structures, An exact formula for the move-to-front rule for self-organizing lists, Arboral satisfaction: recognition and LP approximation, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, A complexity O(1) priority queue for event driven molecular dynamics simulations, Proximate point searching, Advances on sorting by reversals, Randomized search trees, Randomized algorithms for metrical task systems, Fibonacci BSTs: a new balancing method for binary search trees, On compressing permutations and adaptive sorting, A priority queue with the time-finger property, A study on splay trees, Better analysis of binary search tree on decomposable sequences, Demand-aware network designs of bounded degree, Sharing video on demand, I/O efficient dynamic data structures for longest prefix queries, A distribution-sensitive dictionary with low space overhead, Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees, Layered working-set trees, On \(k\)-convex polygons, Slow optimally balanced search strategies vs. cached fast uniformly balanced search strategies, Simplified linear-time Jordan sorting and polygon clipping, Revisiting priority queues for image analysis, Faster algorithms for stable allocation problems, The \(k\)-server problem, Stochastic rearrangement rules for self-organizing data structures, Online algorithms for searching and exploration in the plane, When a dollar makes a BWT, Towards a real time algorithm for parameterized longest common prefix computation, Dynamic algorithms for monotonic interval scheduling problem, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Self-adjusting multi-way search trees, LS(graph): a constraint-based local search for constraint optimization on trees and paths, An introduction to randomized algorithms, Finding minimum-cost flows by double scaling, Three priority queue applications revisited, Amortized complexity verified, Maintaining bridge-connected and biconnected components on-line, A time-efficient, linar-space local similarity algorithm, On the deque conjecture for the splay algorithm, A \(k\)-level data structure for large-scale traveling salesman problems, Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN, An application of program unification to priority queue vectorization, Complexity of algorithm and operations on trees, Data structures for halfplane proximity queries and incremental Voronoi diagrams, Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying, The CB tree: a practical concurrent self-adjusting search tree, A systematic analysis of splaying, Maintaining dynamic minimum spanning trees: an experimental study, Tight bounds for online stable sorting, Sorting streamed multisets, Sorting signed permutations by reversals, revisited, A profile-based tool for finding pipeline parallelism in sequential programs, Biased predecessor search, The power and limitations of static binary search trees with lazy finger, Optimal state-space lumping in Markov chains, The derivation of a tighter bound for top-down skew heaps, An O(n log n)-algorithm for solving a special class of linear programs, Improved algorithms for the multicut and multiflow problems in rooted trees, An improved kernel size for rotation distance in binary trees, A tight amortized bound for path reversal, Approximation algorithms for the shortest common superstring problem, The longest almost-increasing subsequence, On the sequential access theorem and deque conjecture for splay trees, Unfair problems and randomized algorithms for metrical task systems, Finger search in grammar-compressed strings, A new algorithm for Jordan sorting: Its average-case analysis, Heaps and heapsort on secondary storage, Linking and cutting spanning trees, Diameter estimates for graph associahedra, On list update and work function algorithms., Incremental convex planarity testing, Manipulating multiple stacks with ordered-heap, Self-adjusting grid networks to minimize expected path length, Parameterized analysis of paging and list update algorithms, Randomized splay trees: Theoretical and experimental results., Sequential access in splay trees takes linear time, A workbench for computational geometry
