Список заданий по АиСД-year2015-сем2

<wikitex>

Алгоритмы и структуры данных, 1 семестр

1. Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$.
2. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
3. Докажите, что если сделать splay ко всем элементам в порядке возрастания ключа, то суммарное время работы будет $O(n)$.
4. Постройте дерево из хотя бы 7 вершин, которое после операции splay к одному из самых глубоких листьев становится бамбуком.
5. В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
6. Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
7. Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$, а известен только ее ключ, с $O(1)$ дополнительной памяти.

</wikitex>