Структуры данных и модели вычислений
и правое вращения можно осуществить
- Покажите, что левое и правое вращения можно осуществить за время .
- Напишите процедурыи , реализующие левое и правое вращение в дереве относительно узла .
- Пусть,и — произвольные узлы в поддеревьях,ина рис. 10.1 (справа). Как изменится глубина,и при выполнении левого вращения?
- Покажите, что произвольное двоичное дерево поиска с узлами может быть преобразовано в любое другое дерево с тем же числом узлов (и теми же ключами) с помощью вращений. (Указание: сначала покажите, что правых вращений достаточно, чтобы преобразовать любое дерево в идущую вправо цепочку.)
- Напишите процедуры Insert(T, x) и Delete(T, x), которые добавляют и удаляют элемент x из дерева T за время .
- Разработайте алгоритм объединения двух красно-черных деревьев в одно красно-черное дерево за время .
