Рис. 14.7 Четыре случая, возможных в основном цикле процедуры RB-DELETE-FlXUP. Чёрные вершины показаны как чёрные, красные показаны тёмно-серыми. Светло-серые вершины на рисунке могут быть и красными, и чёрными. (Их цвета обозначаются с и с.) Буквы а,/3, . . . обозначают произвольные поддеревья. В каждом случае конфигурация слева преобразуется в конфигурацию справа перекрашиванием вершин и/или вращениями. Вершина, на которую указывает х, дважды чёрная. Единственный случай, когда выполнение цикла продолжается - случай 2. (а) Случай 1 сводится к случаю 2, 3 или 4, если поменять местами цвета вершин В и D и произвести левое вращение, (б) В случае 2 «избыток черноты» в вершине х перемещается вверх по дереву, когда мы делаем D красной и устанавливаем указатель х в В. Если мы попали в случай 2 из случая 1, то цикл завершается, так как вершина В была красной, (в) Случай 3 сводится к случаю 4, если поменять местами цвета вершин С и D и выполнить правое вращение, (г) В случае 4 можно перекрасить некоторые вершины и выполнить левое вращение (не нарушив RB-свойства) так, что лишний чёрный цвет исчезает, и цикл можно завершить.

Задачи к главе 14

283

черноты» вершины цвета с, считая count (с) равным 0 для красной вершины и 1 для чёрной.

14.4-6 Предположим, что вершина вставлена в красно-чёрное дерево, а потом сразу же удалена. Будет ли получившееся дерево совпадать с исходным? Почему?

Задачи

14-1 Динамические множества с сохранением предыдущих версий

Иногда полезно сохранять предыдущие версии меняющегося множества. (Такие структуры данных называются по-английски persistent data structures.) Можно, конечно, копировать множество каждый раз, когда оно изменяется. Но такой подход требует много памяти и времени - и есть способы, позволяющие сделать это более эффективно.

Мы хотим предусмотреть возможность хранения предыдущих версий для множества S с операциями Insert, Delete и Search. Мы считаем, что множество S реализовано с помощью двоичных деревьев поиска, как показано на рис. 14.8а. Для каждой версии множества мы храним свой отдельный корень. Чтобы добавить ключ 5, мы создаём новую вершину с этим ключом. Эта вершина становится левым ребёнком новой вершины с ключом 7, так как существующую вершину менять нельзя. Подобным образом новая вершина с ключом 7 становится левым ребёнком новой вершины с ключом 8, правый ребёнок которой - существующая вершина с ключом 10. В свою очередь, новая вершина с ключом 8 становится правым ребёнком нового корня г с ключом 4, левый ребёнок которого - существующая вершина с ключом 3. Таким образом, мы копируем лишь часть дерева, а в остальном используем старое, как это показано на рис. 14.86.

Мы предполагаем, что вершины дерева содержат поля key, left и right, но не содержат поля р, указывающего на родителя. (См. также упр. 14.3-6.)

а.Покажите, какие вершины хранимого таким образом дерева должны быть изменены (созданы) в общем случае при добавлении или удалении элемента.

б.Напишите процедуру Persistent-Tree-Insert, которая добавляет ключ к в дерево Т.

в.Если высота дерева равна h, сколько времени и памяти требует написанная вами процедура? (Количество памяти можно измерять количеством новых вершин.)

г.Пусть мы используем и поля р в вершинах дерева. В этом случае процедура Persistent-Tree-Insert должна будет выполнить

Рис. 14.8 (а) Двоичное дерево поиска с ключами 2,3,4,7,8,10. (б) Дерево с сохранением предыдущих версий после добавления ключа 5. Текущая версия состоит из вершин, доступных из текущего корня г, а предыдущая версия содержит вершины, доступные из старого корня г. Тёмно-серые вершины добавлены при добавлении ключа 5.

дополнительные действия. Покажите, что в этом случае время работы и объём необходимой памяти будут Г2(га), где га - количество вершин в дереве.

д. Покажите, как можно использовать красно-чёрные деревья, чтобы гарантировать, что добавление и удаление элемента для множества с хранением предыдущих версий будут требовать времени О (lgra) в худшем случае.

14-2 Операция объединения красно-чёрных деревьев

Операция объединения (join) применяется к двум динамическим множествам Si и 5*2 и элементу ж, причём заранее известно, что key[xi] кеу[х] кеу[х2~\ для любых xi G Si и х2 G 5*2. Её результатом является множество S = Si U {ж} U 5*2. В этой задаче мы покажем, как реализовать операцию объединения для красно-чёрных деревьев.

а. Мы будем хранить чёрную высоту красно-чёрного дерева Г в специальной переменной bh[T]. Убедитесь, что это значение можно поддерживать, не размещая никакой дополнительной информации в вершинах дерева и не ухудшая асимптотику времени работы процедур RB-Insert и RB-Delete. Покажите, что, спускаясь по дереву, можно вычислить чёрную высоту каждой вершины за время 0(1) в расчёте на каждую просмотренную вершину.

Мы хотим реализовать операцию RB-Join(Ti, ж, Т2), которая из двух деревьев Т\ и Т2 формирует новое красно-чёрное дерево Г = Ti U {ж} U Т2 (старые деревья при этом разрушаются). Пусть га - общее количество вершин в Т\ и Т2.