Persistent weak-AVL trees

• Název práce v češtině: Persistentní weak-AVL stromy
• Název v anglickém jazyce: Persistent weak-AVL trees
• Klíčová slova: Persistence|Weak-AVL stromy|Rankově vyvážené stromy
• Klíčová slova anglicky: Persistence|Weak-AVL trees|Rank-balanced trees
• Akademický rok vypsání: 2020/2021
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Mareš, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 26.02.2021
• Datum zadání: 26.02.2021
• Datum potvrzení stud. oddělením: 16.03.2021
• Datum a čas obhajoby: 02.07.2021 09:00
• Datum odevzdání elektronické podoby: 27.05.2021
• Datum odevzdání tištěné podoby: 27.05.2021
• Datum proběhlé obhajoby: 02.07.2021
• Oponenti: Mgr. Vladan Majerech, Dr.

Zásady pro vypracování

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.

Seznam odborné literatury

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.