✦ LIBER ✦

Efficient rebalancing of chromatic search trees

✍ Scribed by Joan Boyar; Kim S. Larsen

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 827 KB
Volume: 49
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(05)80075-3

No coin nor oath required. For personal study only.

✦ Synopsis

Chromatic trees were defined by Nurmi and Soisalon-Soininen, as a new type of binary search tree for databases. The aim is to improve runtime performance by allowing a greater degree of concurrency, which, in turn, is obtained by uncoupling updating from rebalancing. This also allows rebalancing to be postponed completely or partially until after peak working hours. The advantages of the proposal of Nurmi and Soisalon-Soininen are quite significant, but there are definite problems with it. First, they give no explicit upper bound on the complexity of their algorithm. Second, some of their rebalancing operations can be applied many more times than necessary. Third, some of their operations, when removing one problem, create another. We define a new set of rebalancing operations which we prove give rise to at most [_logz(N+ 1)J--1 rebalancing operations per insertion and at most [_log/(N+ 1)J-2 rebalancing operations per deletion, where N is the maximum size the tree could ever have, given its initial size and the number of insertions performed. Most of these rebalancing operations, in fact, do no restructuring; they simply move weights around. The number of operations which actually change the structure of the tree is at most one per update.

📜 SIMILAR VOLUMES

Efficient multiway radix search trees

✍ Úlfar Erlingsson; Mukkai Krishnamoorthy; T.V. Raman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 551 KB

We present a new scheme for building static search trees, using multiway radix search. We apply this method to me problem of code generation for switch statements in imperative languages. For sparse case sets, the method has an advantage over existing methods, empirically requiring fewer than three

Chromatic polynomials of generalized tre

Chromatic polynomials of generalized trees

✍ Earl Glen Whitehead Jr. 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Amortization Results for Chromatic Searc

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues

✍ Joan Boyar; Rolf Fagerberg; Kim S Larsen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 396 KB

The intention in designing data structures with relaxed balance, such as chromatic search trees, is to facilitate fast updating on shared-memory asynchronous parallel architectures. To obtain this, the updating and rebalancing have been uncoupled, so extensive locking in connection with updates is a

Chromaticity of two-trees

✍ Earl Glen Whitehead Jr. 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

Induced trees in graphs of large chromat

Induced trees in graphs of large chromatic number

✍ Scott, A. D. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB 👁 2 views

Gyárfás and Sumner independently conjectured that for every tree T and integer k there is an integer f (k, T ) such that every graph G with χ(G) > f(k, t) contains either K k or an induced copy of T . We prove a `topological´version of the conjecture: for every tree T and integer k there is g(k, T )

Minimal trees of given search number

✍ Jonathan D.H. Smith 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 717 KB

A recurrence relation and asymptotic estimate for the number of minimal trees of given search number are derived. In addition, a language for describing these trees and structures within them is developed. Their automorphisms groups are also discussed.