uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
General balanced trees
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. Datalogi.
1999 (Engelska)Ingår i: Journal of Algorithms, Vol. 30, s. 1-28Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We show that, in order to achieve efficient maintenance of a balanced binary search tree, no shape restriction other than a logarithmic height is required. The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes. Thus, in the case when amortized bounds are sufficient, there is no need for sophisticated balance criteria.

The maintenance algorithms use partial rebuilding. This is important for certain applications, and has previously been used with weight-balanced trees. We show that the amortized cost incurred by general balanced trees is lower than what has been shown for weight-balanced trees.

Ort, förlag, år, upplaga, sidor
1999. Vol. 30, s. 1-28
Nyckelord [en]
binary search trees, search trees, general balanced trees
Identifikatorer
URN: urn:nbn:se:uu:diva-25785OAI: oai:DiVA.org:uu-25785DiVA, id: diva2:53559
Tillgänglig från: 2007-02-13 Skapad: 2007-02-13 Senast uppdaterad: 2011-01-14

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Andersson, Arne

Sök vidare i DiVA

Av författaren/redaktören
Andersson, Arne
Av organisationen
Institutionen för informationsteknologiDatalogi

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 890 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf