Dynamické vlastnosti stromů

• Název práce v češtině: Dynamické vlastnosti stromů
• Název v anglickém jazyce: Dynamic properties of trees
• Klíčová slova: binární vyhledávací stromy|červenočerné stromy|tango stromy|splay stromy|multisplay stromy
• Klíčová slova anglicky: binary search trees|Red-Black trees|Tango trees|Splay trees|Multisplay trees
• Akademický rok vypsání: 2020/2021
• Typ práce: diplomová práce
• Jazyk práce: češ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í: 20.04.2021
• Datum zadání: 27.04.2021
• Datum potvrzení stud. oddělením: 18.05.2021
• Datum a čas obhajoby: 02.02.2022 09:00
• Datum odevzdání elektronické podoby: 05.01.2022
• Datum odevzdání tištěné podoby: 06.01.2022
• Datum proběhlé obhajoby: 02.02.2022
• Oponenti: Mgr. Ondřej Mička

Zásady pro vypracování

Cílem práce je prozkoumat známé výsledky o variantách vyhledávacích stromů
aproximujících dynamicky optimální strom: například Tango stromy a Multi-splay
stromy. Tyto datové struktury vyzkoušet implementovat a experimentálně srovnat
jejich vlastnosti.

Seznam odborné literatury

Wang, Derryberry, Sleator. (log log N)-competitive dynamic binary search trees. In Proceedings of SODA, pages 374–383, 2006.

Demaine et al. The geometry of binary search trees. In Proceedings of SODA, pages 496-505, 2009.

Wang. Multi-splay trees. PhD Thesis at Carnegie Mellon University, 2006.