Variants of (a,b)-Trees with Relaxed Balance

Lars Jacobsen; Kim Skak Larsen

doi:10.1142/S012905410100059X

Variants of (a,b)-Trees with Relaxed Balance

Lars Jacobsen
, Kim Skak Larsen

Syddansk Universitet

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

New variants of (a,b)-trees with relaxed balance are proposed. These variants have better space utilization than the earlier proposals, while the asymptotic complexity of rebalancing is unchanged. The proof of complexity, which is derived, is much simpler than the ones previously published. Through experiments, some of the most interesting applications of this data structure are modeled, and it is demonstrated that the new variants are competitive.

Originalsprog	Engelsk
Tidsskrift	International Journal of Foundations of Computer Science
Vol/bind	12
Udgave nummer	4
Sider (fra-til)	455-478
Antal sider	24
ISSN	0129-0541
DOI	https://doi.org/10.1142/S012905410100059X
Status	Udgivet - 2001

Dokumenter og links

10.1142/S012905410100059X

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@article{1256e1f041db11dd9fbe000ea68e967b,

title = "Variants of (a,b)-Trees with Relaxed Balance",

abstract = "New variants of (a,b)-trees with relaxed balance are proposed. These variants have better space utilization than the earlier proposals, while the asymptotic complexity of rebalancing is unchanged. The proof of complexity, which is derived, is much simpler than the ones previously published. Through experiments, some of the most interesting applications of this data structure are modeled, and it is demonstrated that the new variants are competitive.",

author = "Lars Jacobsen and Larsen, \{Kim Skak\}",

year = "2001",

doi = "10.1142/S012905410100059X",

language = "English",

volume = "12",

pages = "455--478",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific",

number = "4",

}

TY - JOUR

T1 - Variants of (a,b)-Trees with Relaxed Balance

AU - Jacobsen, Lars

AU - Larsen, Kim Skak

PY - 2001

Y1 - 2001

N2 - New variants of (a,b)-trees with relaxed balance are proposed. These variants have better space utilization than the earlier proposals, while the asymptotic complexity of rebalancing is unchanged. The proof of complexity, which is derived, is much simpler than the ones previously published. Through experiments, some of the most interesting applications of this data structure are modeled, and it is demonstrated that the new variants are competitive.

AB - New variants of (a,b)-trees with relaxed balance are proposed. These variants have better space utilization than the earlier proposals, while the asymptotic complexity of rebalancing is unchanged. The proof of complexity, which is derived, is much simpler than the ones previously published. Through experiments, some of the most interesting applications of this data structure are modeled, and it is demonstrated that the new variants are competitive.

U2 - 10.1142/S012905410100059X

DO - 10.1142/S012905410100059X

M3 - Journal article

SN - 0129-0541

VL - 12

SP - 455

EP - 478

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 4

ER -

Variants of (a,b)-Trees with Relaxed Balance

Abstract

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater