Список заданий по АиСД-year2015-сем2 — различия между версиями
(Новая страница: «<wikitex> = Алгоритмы и структуры данных, 1 семестр = # Покажите, что если в сплей дереве при опе...») |
|||
| Строка 1: | Строка 1: | ||
<wikitex> | <wikitex> | ||
| − | = Алгоритмы и структуры данных, | + | = Алгоритмы и структуры данных, 2 семестр = |
# Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$. | # Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$. | ||
# Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось? | # Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось? | ||
Версия 15:02, 23 февраля 2016
<wikitex>
Алгоритмы и структуры данных, 2 семестр
- Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$.
- Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
- Докажите, что если сделать splay ко всем элементам в порядке возрастания ключа, то суммарное время работы будет $O(n)$.
- Постройте дерево из хотя бы 7 вершин, которое после операции splay к одному из самых глубоких листьев становится бамбуком.
- В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
- Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
- Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$, а известен только ее ключ, с $O(1)$ дополнительной памяти.
</wikitex>
