Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 517894.0, MPI für Informatik / Algorithms and Complexity Group
Finger Search Trees with Constant Update Time
Authors:Brodal, Gerth Stølting
Language:English
Publisher:ACM Press / SIAM
Place of Publication:New York, USA
Date of Publication (YYYY-MM-DD):1998
Title of Proceedings:Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98)
Start Page:540
End Page:549
Place of Conference/Meeting:San Francisko, USA
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
1998
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:We consider the problem of implementing finger search trees on the
pointer machine, {\it i.e.}, how to maintain a sorted list such that
searching for an element $x$, starting the search at any arbitrary
element $f$ in the list, only requires logarithmic time in the
distance between $x$ and $f$ in the list.

We present the first pointer-based implementation of finger search
trees allowing new elements to be inserted at any arbitrary position
in the list in worst case constant time. Previously, the best known
insertion time on the pointer machine was $O(\log^{*} n)$, where $n$
is the total length of the list. On a unit-cost RAM, a constant
insertion time has been achieved by Dietz and Raman by using
standard techniques of packing small problem sizes into a constant
number of machine words.

Deletion of a list element is supported in $O(\log^{*} n)$ time, which
matches the previous best bounds. Our data structure requires linear
space.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-F7F4FED03445DDFFC12565B70057C405-...
ISBN:0-89871-410-9
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.