Изменения
sta
# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
# Для каких $a$ определен $\log^*_a x$?
# Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$?
# АВЛ-дерево: у каждой вершины высота левого и правого поддерева различается не более чем на 1. Докажите, что высота АВЛ-дерева есть $O(\log n)$
# Докажите, что после добавления элемента в АВЛ дерево можно восстановить баланс за $O(1)$ балансировок.
# Предложите алгоритм удаления из АВЛ-дерева.
# Красно-черное дерево: все вершины красные или черные, у красной вершины не может быть красного родителя, черная высота любой свободной позиции (отсутствующего сына вершины) одинаковая. Докажите, что высота красно-черного дерева есть $O(\log n)$
# Предложите алгоритм добавления в красно-черное дерево
# Предложите алгоритм удаления из красно-черного дерева
# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
# Мальчик Петя в предыдущей задаче предложил построить декартово дерево с приоритетом $p[i]$. Приведите контрпример.
# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
# Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
# В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
</wikitex>
