Деревья поиска

Пятница, 01 марта 2013

ФМЛ 239, Актовый зал

Описание

Splay-деревья [Self Adjusting BST], [Wikipedia]
Амортиризированная оценка O(log W/w(x)) на splay
Оптимальное статическое дерево поиска, построение с помощью ДП
Статическая оптимальность splay-деревьев
Оптимальность splay-деревьев относительно локальных запросов
Геометрическое представление работы с BST, Arborally-satisfied sets
TANGO-деревья [Dynamic Optimality—Almost], [Wikipedia]