Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
An Optimized Representation for Dynamic k-ary Cardinal Trees
Blekinge Tekniska Högskola, Sektionen för datavetenskap och kommunikation.
2009 (Engelska)Självständigt arbete på avancerad nivå (masterexamen)Studentuppsats (Examensarbete)
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.

Ort, förlag, år, upplaga, sidor
2009. , s. 45
Nyckelord [en]
Succinct data structures, binary trees, ordinal trees, cardinal trees, rank, select, static and dynamic.
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:bth-2199Lokalt ID: oai:bth.se:arkivex133C783533766566C12575D70073C7F7OAI: oai:DiVA.org:bth-2199DiVA, id: diva2:829466
Uppsök
teknik
Handledare
Tillgänglig från: 2015-04-22 Skapad: 2009-06-16 Senast uppdaterad: 2025-09-30Bibliografiskt granskad

Open Access i DiVA

fulltext(1215 kB)229 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1215 kBChecksumma SHA-512
f6c45c2c413a6361b9a3362f28f60cffcdb76c3d1be9823f7461ae16d8380da3a7ba8ef6983db2ebb03c6a0cb358741961c132161211cf071814b53c16b21115
Typ fulltextMimetyp application/pdf

Av organisationen
Sektionen för datavetenskap och kommunikation
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 229 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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