Search Trees with Relaxed Balance and Near-Optimal Height

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + ε)log2n + 1, for any g > 0. The rebalancing work is amortized O(1/ε) per update. This is the first binary search tree with relaxed balance having a height bound better than c · log2 n for a fixed constant c. In all previous proposals, the constant is at least 1/log2 φ τ; 1.44, where φ is the golden ratio. As a consequence, we can also define a standard (non-relaxed) k-tree with amortized constant rebalancing per update, which is an improvement over the original definition. Search engines based on main-memory databases with strongly fluctuating workloads are possible applications for this line of work.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures, 7th International Workshop, WADS 2001
Number of pages12
Publication date2001
Pages414-425
DOIs
Publication statusPublished - 2001
EventSeventh International Workshop on Algorithms and Data Structures - Providence, United States
Duration: 8. Aug 200110. Aug 2001

Conference

ConferenceSeventh International Workshop on Algorithms and Data Structures
Country/TerritoryUnited States
CityProvidence
Period08/08/200110/08/2001
SeriesLecture Notes in Computer Science
Volume2125

Fingerprint

Dive into the research topics of 'Search Trees with Relaxed Balance and Near-Optimal Height'. Together they form a unique fingerprint.

Cite this