Original title: Persistentní weak-AVL stromy
Translated title: Persistent weak-AVL trees
Authors: Škrobánek, Jiří ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
Document type: Bachelor's theses
Year: 2021
Language: eng
Abstract: This thesis investigates persistence (i.e., preservation of data by updates) of binary search trees. In particular, we explore how weak-AVL trees may be converted into efficient fully-persistent data structures. After mentioning all important properties of weak-AVL trees, we present a new method to store them with worst-case constant number of changes per update. Then we show some general schemes for conversion of binary search trees (and possibly other pointer-based data structures) into their persistent variants. Finally the established theory is used to obtain fully-persistent weak-AVL trees.
Keywords: Persistence|Weak-AVL trees|Rank-balanced trees; Persistence|Weak-AVL stromy|Rankově vyvážené stromy

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/127952

Permalink: http://www.nusl.cz/ntk/nusl-448217


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses