Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 DetailsÜbersicht
  Finger Search Trees with Constant Update Time

Brodal, G. S. (1998). Finger Search Trees with Constant Update Time. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98) (pp. 540-549). New York, USA: ACM Press / SIAM.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3795-1 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3796-0
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Brodal, Gerth Stølting1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021998
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : ACM Press / SIAM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 517894
Anderer: Local-ID: C1256428004B93B8-F7F4FED03445DDFFC12565B70057C405-Brodal98a
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: San Francisko, USA
Start-/Enddatum: 1998

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM Press / SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 540 - 549 Identifikator: ISBN: 0-89871-410-9