Persistent weak-AVL trees

• Thesis title in Czech: Persistentní weak-AVL stromy
• Thesis title in English: Persistent weak-AVL trees
• Key words: Persistence|Weak-AVL stromy|Rankově vyvážené stromy
• English key words: Persistence|Weak-AVL trees|Rank-balanced trees
• Academic year of topic announcement: 2020/2021
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 26.02.2021
• Date of assignment: 26.02.2021
• Confirmed by Study dept. on: 16.03.2021
• Date and time of defence: 02.07.2021 09:00
• Date of electronic submission: 27.05.2021
• Date of submission of printed version: 27.05.2021
• Date of proceeded defence: 02.07.2021
• Opponents: Mgr. Vladan Majerech, Dr.

Guidelines

Driscoll et al. navrhli persistentní vyhledávací stromy založené na worst-case variantě červeno-černých stromů. Konstrukce je značně komplikovaná. Cílem práce je prozkoumat, zda je možné ji zjednodušit nahrazením červeno-černých stromů rankově vyváženými stromy, zejména weak-AVL stromy.

References

Driscoll, Sarnak, Sleator, Tarjan: Making Data Structures Persistent. Journal of Computer and System Science 38(1), 1989.

Haeupler, Sen, Tarjan: Rank-Balanced Trees, ACM Transactions on Algorithms 11(4), 2015.