Fully Dynamic Search Trees can be Balanced in O(log^2 N) Time (Articolo in rivista)

Type
Label
  • Fully Dynamic Search Trees can be Balanced in O(log^2 N) Time (Articolo in rivista) (literal)
Anno
  • 2002-01-01T00:00:00+01:00 (literal)
Alternative label
  • Barillari, F.; Nardelli, E.; Pepe, M. (2002)
    Fully Dynamic Search Trees can be Balanced in O(log^2 N) Time
    in Journal of parallel and distributed computing (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Barillari, F.; Nardelli, E.; Pepe, M. (literal)
Pagina inizio
  • 1617 (literal)
Pagina fine
  • 1628 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 62 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • number: 11 (literal)
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Fully Dynamic Search Trees can be Balanced in O(log^2 N) Time (literal)
Abstract
  • In this paper we consider the dictionary problem in a message-passing distributed environment. We introduce a new version, based on AVL-trees, of distributed search trees, the first to be fully scalable, that is capable to both grow and shrink as long as keys are inserted and deleted. We prove that in the worst case a key can be inserted, searched or deleted with O(log^2 N) messages. We show that for the introduced distributed search tree this bound is tight. Since the defined structure maintains the relative order of the keys it can support also queries that refer to the linear order of keys, such as nearest neighbor or range queries. (literal)
Prodotto di
Autore CNR

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it