Change search
ReferencesLink to record
Permanent link

Direct link
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. , 45 p.
Keyword [en]
Succinct data structures, binary trees, ordinal trees, cardinal trees, rank, select, static and dynamic.
National Category
Computer Science
URN: urn:nbn:se:bth-2199Local ID: diva2:829466
Available from: 2015-04-22 Created: 2009-06-16 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

By organisation
School of Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 11 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

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link