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