English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A simple balanced search tree with 0(1) worst-case update time

Fleischer, R.(1992). A simple balanced search tree with 0(1) worst-case update time (MPI-I-92-101). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-92-101.pdf (Any fulltext), 121KB
Name:
MPI-I-92-101.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Fleischer, Rudolf1, Author              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: In this paper we show how a slight modification of $(a,b)$-trees allows us to perform member and neighbor queries in $O(\log n)$ time and updates in $O(1)$ worst-case time (once the position of the inserted or deleted key is known). Our data structure is quite natural and much simpler than previous worst-case optimal solutions. It is based on two techniques : 1) \em{bucketing}, i.e.~storing an ordered list of $2\log n$ keys in each leaf of an $(a,b)$ tree, and \quad 2) \em{lazy splitting}, i.e.~postponing necessary splits of big nodes until we have time to handle them. It can also be used as a finger tree with $O(\log^*n)$ worst-case update time.

Details

show
hide
Language(s): eng - English
 Dates: 1992
 Publication Status: Published in print
 Pages: 10 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-92-101
BibTex Citekey: Fleischer92a
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -