English

# 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

show hide
Genre: Report

### 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]
-
-
-

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
Rev. Type: -
Identifiers: Report Nr.: MPI-I-92-101
BibTex Citekey: Fleischer92a
Degree: -

show

show

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: -