Return to search

Dynamické vlastnosti stromů / Dynamic properties of trees

In this thesis we compared some variants of binary search trees that approach dynamic optimality: Tango trees, Multisplay trees, and Splay trees. We empirically tested the behavior of these three types of trees, as well as Red-Black trees. We measured the amount of visited nodes per operation and running time on real hardware. We proved that Tango trees and Multisplay trees are in most cases less efficient than Splay trees and Red-Black trees. Cache-related effects played a surprisingly large part in the behavior of Red-Black tree and Splay tree. 1

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:455999
Date January 2022
CreatorsNěmeček, Viktor
ContributorsMareš, Martin, Mička, Ondřej
Source SetsCzech ETDs
LanguageCzech
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0018 seconds