Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/96540

Concurrent rebalancing of AVL trees: a fine-grained approach
Bougé, Luc; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, Nicolas
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
We address the concurrent rebalancing of almost balanced binary search trees (AVL trees). Such a rebalancing may for instance be necessary after successive insertions and deletions of keys. We show that this problem can be studied through the self-reorganization of distributed systems of nodes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a much simpler algorithm that the ones previously known. As a by-product, this solves in a very general setting an old question raised by H.T. Kung and P.L. Lehman: where should rotations take place to rebalance arbitrary search trees?
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Concurrent rebalancing
AVL trees
Concurrent algorithms
Concurrent insertions and deletions
Concurrent generalized rotations
Safety and liveness proofs
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Bougé, Luc; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier
Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Daniel, Riu
Baeza-Yates, Ricardo; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier
Bouge, L; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, N