и правое вращения можно осуществить

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

Содержание раздела

---

---