We focus on space-efficient, namely succinct, representations of static ordinal unlabeled trees. These structures have space complexity which is optimal up to a lower-order term, yet they support a reasonable set of operations in constant time. This topic has been studied in the last 27 years by numerous authors who came with several distinct solutions to this problem. It is not only of an academic interest, the succinct tree data structures has been used in several data-intensive applications, such as XML processing and representation of suffix trees. In this thesis, we describe the current state of knowledge in this area, compare the many different approaches, and propose several either new or alternative algorithms for operations in the representations alongside. Powered by TCPDF (www.tcpdf.org)
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:352593 |
| Date | January 2016 |
| Creators | Juraszek, Adam |
| Contributors | Mareš, Martin, Majerech, Vladan |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.002 seconds