Изменения
Нет описания правки
u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
# Задано подвешенное дерево. Нужно отвечать на запросы: подвесить вершину как лист к одной из имеющихся вершин, найти наименьшего общего предка двух уже добавленных вершин. Время работы запросов: $O(n \log{n})$.
# Предложите алгоритм добавления в АВЛ-деревоза $O(h)$, где $h$ {{---}} высота дерева.# Предложите алгоритм удаления из АВЛ-дерева за $O(h)$, где $h$ {{---}} высота дерева.# Предложите алгоритм добавления в красно-черное деревоза $O(h)$, где $h$ {{---}} высота дерева.# Предложите алгоритм удаления из красно-черного дереваза $O(h)$, где $h$ {{---}} высота дерева.
# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
# Докажите, что высота красно-черного дерева $O(\log{n})$.
</wikitex>
