Updating a balanced search tree in 0(1) rotations

DOI10.1016/0020-0190(83)90099-6zbMath0508.68041OpenAlexW2011933350MaRDI QIDQ1838042

Robert Endre Tarjan

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(83)90099-6

zbMATH Keywords

balanced search treesred-black treeshalf- balanced binary treessymmetric binary B-trees

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (19)

Computing rectangle enclosures ⋮ How to update a balanced binary tree with a constant number of rotations ⋮ Rank-Balanced Trees ⋮ Amortized Computational Complexity ⋮ Making data structures persistent ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Red-black trees with constant update time ⋮ Binary search trees of almost optimal height ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ On the dynamic maintenance of maximal points in the plane ⋮ Maintaining multiple representations of dynamic data structures ⋮ Parallel algorithms for red--black trees ⋮ Optimal finger search trees in the pointer machine ⋮ Dynamic interpolation search revisited ⋮ Unnamed Item ⋮ A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon ⋮ A new approach to the dynamic maintenance of maximal points in a plane ⋮ A dynamic fixed windowing problem

Cites Work

• On the relationship between son-trees and symmetric binary B-trees
• A new data structure for representing sorted lists
• Symmetric binary B-trees: Data structure and maintenance algorithms
• Priority Search Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Updating a balanced search tree in 0(1) rotations