Optimal finger search trees in the pointer machine

DOI10.1016/S0022-0000(03)00013-8zbMath1072.68033MaRDI 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

Complexity; Data structures; Balanced search trees

Mathematics Subject Classification ID

68P10: Searching and sorting

68P05: Data structures

Related Items

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

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