Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An Optimized Representation for Dynamic k-ary Cardinal Trees
Blekinge Institute of Technology, School of Computing.
2009 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
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.

Place, publisher, year, edition, pages
2009. , p. 45
Keywords [en]
Succinct data structures, binary trees, ordinal trees, cardinal trees, rank, select, static and dynamic.
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-2199Local ID: oai:bth.se:arkivex133C783533766566C12575D70073C7F7OAI: oai:DiVA.org:bth-2199DiVA, id: diva2:829466
Uppsok
Technology
Supervisors
Available from: 2015-04-22 Created: 2009-06-16 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

fulltext(1215 kB)197 downloads
File information
File name FULLTEXT01.pdfFile size 1215 kBChecksum SHA-512
f6c45c2c413a6361b9a3362f28f60cffcdb76c3d1be9823f7461ae16d8380da3a7ba8ef6983db2ebb03c6a0cb358741961c132161211cf071814b53c16b21115
Type fulltextMimetype application/pdf

By organisation
School of Computing
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 197 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 195 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf