Структуры данных и модели вычислений

         

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


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


Содержание  Назад  Вперед