A constant update time finger search tree

DOI10.1016/0020-0190(94)00115-4zbMath0938.68586OpenAlexW1993762176WikidataQ127526108 ScholiaQ127526108MaRDI QIDQ1338781

Paul F. Dietz, Rajeev Raman

Publication date: 26 February 1996

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

Full work available at URL: http://hdl.handle.net/1802/5280

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)

Related Items

Binary search trees: How low can you go?, ISB-tree: A new indexing scheme with efficient expected behaviour, Improved bounds for finger search on a RAM, Optimal finger search trees in the pointer machine, Finger search in grammar-compressed strings, A History of Distribution-Sensitive Data Structures, Improved Dynamic Graph Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• A linear-time algorithm for a special case of disjoint set union
• A balanced search tree O(1) worst-case update time
• Making data structures persistent
• A new data structure for representing sorted lists
• Surpassing the information theoretic bound with fusion trees
• Randomized search trees
• Fast Algorithms for Finding Nearest Common Ancestors
• AVL-trees for localized search
• Hash functions for priority queues
• Design and Analysis of a Data Structure for Representing Sorted Lists
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME