Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Optimized Representation for Dynamic k-ary Cardinal Trees
Blekinge Tekniska Högskola, Sektionen för datavetenskap och kommunikation.
2009 (engelsk)Independent thesis Advanced level (degree of Master (Two Years))Oppgave
Abstract [en]

Trees are one of the most fundamental structures in computer science. Standard pointer-based representations consume a significant amount of space while only supporting a small set of navigational operations. Succinct data structures have been developed to overcome these difficulties. A succinct data structure for an object from a given class of objects occupies space close to the information-theoretic lower-bound for representing an object from the class, while supporting the required operations on the object efficiently. In this thesis we consider representing trees succinctly. Various succinct representations have been designed for representing different classes of trees, namely, ordinal trees, cardinal trees and labelled trees. Barring a few, most of these representations are static in that they do not support inserting and deleting nodes. We consider succinct representations for cardinal trees that also support updates (insertions and deletions), i.e., dynamic cardinal trees. A cardinal tree of degree k, also referred to as a k-ary cardinal tree or simply a k-ary tree is a tree where each node has place for up to k children with labels from 1 to k. The information-theoretic lower bound for representing a k-ary cardinal tree on n nodes is roughly (2n+n log k) bits. Representations that take (2n+n log k+ o(n log k ) ) bits have been designed that support basic navigations operations like finding the parent, i-th child, child-labeled j, size of a subtree etc. in constant time. But these could not support updates efficiently. The only known succinct dynamic representation was given by Diego, who gave a structure that still uses (2n+n log k+o(n log k ) ) bits and supports basic navigational operations in O((log k+log log n) ) time, and updates in O((log k + log log n)(1+log k /log (log k + log log n))) amortized time. We improve the times for the operations without increasing the space complexity, for the case when k is reasonably small compared to n. In particular, when k=(O(√(log n ))) our representation supports all the navigational operations in constant time while supporting updates in O(√(log log n )) amortized time.

sted, utgiver, år, opplag, sider
2009. , s. 45
Emneord [en]
Succinct data structures, binary trees, ordinal trees, cardinal trees, rank, select, static and dynamic.
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-2199Lokal ID: oai:bth.se:arkivex133C783533766566C12575D70073C7F7OAI: oai:DiVA.org:bth-2199DiVA, id: diva2:829466
Uppsök
Technology
Veileder
Tilgjengelig fra: 2015-04-22 Laget: 2009-06-16 Sist oppdatert: 2025-09-30bibliografisk kontrollert

Open Access i DiVA

fulltekst(1215 kB)228 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1215 kBChecksum SHA-512
f6c45c2c413a6361b9a3362f28f60cffcdb76c3d1be9823f7461ae16d8380da3a7ba8ef6983db2ebb03c6a0cb358741961c132161211cf071814b53c16b21115
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 228 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 315 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf