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