Title:
|
Concurrent rebalancing on hyperred-black trees
|
Author:
|
Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Daniel, Riu
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
The HyperRed-Black trees are a relaxed version of Red-Black
trees accepting high degree of concurrency. In the Red-Black trees
consecutive red nodes are forbidden. This restriction has been
withdrawn in the Chromatic trees. They have been introduced by
O.~Nurmi and E.~Soisalon-Soininen to work in a concurrent
environment. A Chromatic tree can have big clusters of red nodes
surrounded by black nodes. Nevertheless, concurrent rebalancing of
Chromatic trees into Red-Black trees has a serious drawback:
in big cluster of red nodes only the top node can be updated. Direct
updating inside the cluster is forbidden. This approach gives us
limited degree of concurrency. The HyperRed-Black trees has been
designed to solve this problem. It is possible to update red nodes in
the inside of a red cluster. In a HyperRed-Black tree nodes can
have a multiplicity of colors; they can be red, black or hyper-red. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -HyperRed-Black trees -Chromatic tree -Red-black trees |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|