Optimal finger search trees in the pointer machine

DOI10.1016/S0022-0000(03)00013-8zbMath1072.68033OpenAlexW4210692195MaRDI QIDQ5917584

Christos Makris, George Lagogiannis, Kostas Tsichlas, Gerth Stølting Brodal, Athanasios K. Tsakalidis

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00013-8

zbMATH Keywords

ComplexityData structuresBalanced search trees

Mathematics Subject Classification ID

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

Related Items

Improved bounds for finger search on a RAM ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ Fast local searches and updates in bounded universes ⋮ Some Results for Elementary Operations ⋮ Finger search in grammar-compressed strings ⋮ A History of Distribution-Sensitive Data Structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• A balanced search tree O(1) worst-case update time
• Making data structures persistent
• A new data structure for representing sorted lists
• A constant update time finger search tree
• Updating a balanced search tree in 0(1) rotations
• Tight(er) worst-case bounds on dynamic searching and priority queues
• AVL-trees for localized search
• Sorting jordan sequences in linear time using level-linked search trees
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME

This page was built for publication: Optimal finger search trees in the pointer machine