Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 74
Текст из файла (страница 74)
После этого, так как у нас нет двух идущих подряд красных узлов, работа процедуры завершается. Больше тело цикла тчййе не выполняется, так как узел «. р теперь черный. Покажем, что случаи 2 и 3 сохраняют инвариант цикла. (Как мы только что доказали, перед следующей проверкой в строке 1 узел «. р будет черным и тело цикла больше выполняться не будет.) а. В случае 2 выполняется присвоение, после которого «указывает на красный узел «.р.
Никаких других изменений «или его цвета в случаях 2 и 3 не выполняется. б. В случае 3 узел «. р делается черным, так что если «.р в начале следующей итерации является корнем, то этот корень — черный. в. Как и в случае 1, в случаях 2 и 3 свойства 1, 3 и 5 сохраняются.
Поскольку узел «в случаях 2 и 3 не является корнем, нарушение свойства 2 невозможна Случаи 2 и 3 не могут приводить к нарушению свойства 2. 355 Глава !5. Красно-черные деревья посюльку при повороте в случае 3 сделанный красным узел становится дочерним по отношению к черному. Таким образом, случаи 2 и 3 приводят к юррекции нарушения свойства 4, при этом не внося никаких новых нарушений красно-черных свойств. Показав, что при любой итерации инвариант цикла сохраняется, мы тем самым показали, что процедура КВ-1ь~еект-Р!х!5р корректно восстанавливает красно- черные свойства дерева. Анализ Чему равно время работы процедуры КВ-1изекту Поскольку высота краске-черного дерева с и узлами равна О(18 и), выполнение строк 1-16 процедуры кВ-!хзект требует времени О(18 и).
В процедуре кВ-1мзект-Р!х!5р цикл н'ь!1е повторно выполняется только в случае 1, и указатель г при этом перемещается вверх по дереву на два уровня. Таким образом, общее количество возможных выполнений тела цикла зеййе равно О(!к п). Следовательно, общее время работы процедуры КВ-1нзЕкт равно 0118 п). Интересно, что в ней никогда не выполяяется больше двух поворотов, поскольку цикл и Ь|!е в случаях 2 и 3 завершает работу.
Упражнения 13.3.1 В строке 16 процедуры КВ-1изект мы окрашиваем вновь вставленный узел в красный цвет. Заметим, что если бы мы окрашивали его в черный цвет, то свойство 4 красно-черного дерева не было бы нарушено. Так почему же мы не делаем зтогоу 13.3.2 Изобразите красно-черные деревья, которые образуются при последовательной вставке ключей 41, 38, 31, 12, 19, 8 в изначально пустое красно-черное дерево.
13.3.3 Предположим, что черная высота каждого из поддеревьев а, 13, 2, 6 и е на рис. 13.5 и 13.6 равна Ь. Найдите черные высоты каждого узла на этих рисунках, чтобы убедиться, что свойство 5 сохраняется при указанных преобразованиях. 13.3.4 Профессор озабочен вопросом, не может ли в процедуре КВ-1изект-р!х!л* проюойти присвоение значения кеп узлу Т. пЫ. со1ог, ведь в этом случае проверка в строке 1 не вызовет окончания работы цикла, если г — юрень дерева. Покажите, что страхи профессора безосновательны, доказав, что процедура КВ-1ызеитЕ!х~л' никогда не окрашивает Т. пй. со1ог в красный цвет. Часть 111.
Стррктауры данны 55б 13.3.5 Рассмотрим красно-черное дерево, образованное вставкой и узлов с помощью процедуры КВ-1мзект. Докажите, что если и > 1, то в дереве имеется как минимум один красный узел. 13.3.6 Предложите эффективную реализацию процедуры йВ-11чзект в случае, когда представление красно-черных деревьев не включает указатель на родительский узел. 13.4.
Удаление Как и остальные базовые операции над красно-черными деревьями с и узлами, удаление узла выполняется за время 0(1кп). Удаление оказывается несколько более сложной задачей, чем вставка. Процедура для удаления узла из красно-черного дерева основана на процедуре ТКЕЕ-ПЕЬЕТЕ (раздел 12.3). Сначала нужно внести изменения в подпрограмму ТкАмзРЬАмт, которую процедура Ткее-Пеьете вызывает в процессе работы с красно-черным деревом. кВ-ТкА1чБРьА1чт(Т, и, и) 1 Ии,р==Т.пй 2 Т.гоо1 = и 3 е!яе(ти== и.р.(е1т 4 и.р.(е1'ь = и 5 е1зе и.р.пдЬ1 = и б и.р = и.р Процедура йВ-ТкАмзРЬАмт имеет два отличия от процедуры ТкАмзРЬАмт. Вопервых, строка 1 обращается к ограничителю Т.
пь(, а не к 1ч1ь. Во-вторых, присваивание атрибуту и.р в строке б выполняется безусловно: возможно выполнение присваивания, даже если и указывает на ограничитель. В действительности мы будем использовать возможность присваивания атрибуту и. р при о = Т. пй. Процедура йВ-Пеьете подобна процедуре Ткее-Пеьете, но имеет дополнительные строки псевдокода.
Некоторые из них отслеживают узел у, который может вызвать нарушения красно-черных свойств. Если нужно удалить узел я и г имеет меньше двух дочерних узлов, то з удаляется из дерева, и мы делаем у совпадающим с х. Если у з два дочерних узла, то узел у должен быть преемником а в дереве, и у перемещается в дереве в позицию узла г. Мы также запоминаем цвет у перед его удалением или перемещением и отслеживаем узел х, который перемещается в исходную позицию узла у в дереве, поскольку узел х также может привести к нарушению красно-черных свойств. После удаления узла з процедура 1ЬВ-Пеьете вызывает вспомогательную процедуру КВ-Оеьете-р1хг1Р, которая Гаева !5. Красно-черные деревья 557 изменяет цвета и выполняет повороты для восстановления свойств красно-черно- го дерева.
КВ-Пеьете(Т,г) ! У=г 2 у-опд1иа1-со1от = у. со1от 3 1в г.1е5"с ==Т.п11 4 х = г.пдЫ 5 НВ-ТКАХБРЬАХТ(Т, г, г. пдЫ) б е!яе(в г. пдЫ == Т. п11 7 х = г.!етг 8 ХВ-ТклхБРелхт(Т, г, г, 1е(1) 9 е1яе у = Ткее-М1х1мим(г. пдЬ1) !О у-опд1па1-со1от = у. со1от П х = у.пдЫ !2 !ау р==г !3 яр=у !4 е!яе КВ-Тклхзи.лхт(Т, у, у. пдЬ1) !5 у.пдЫ = г.пдЫ !6 у.пдЬ1.р = у !7 КВ-ТКАХБРЕАХТ(Т, г,у) !8 у.1е52 = г.1еГс !9 У.1е5"1.р = у 20 у.со1от = г.со1от 2! !Т у-опдта1-со!от == НЕЛСК 22 КВ-Рееете-р!х15Р(Т,г) Хотя процедура КВ-13н.ете содержит почти в два раза больше строк, чем псевдокод ТКЕЕ-13ЕЕЕТЕ, обе зти процедуры имеют одинаковую базовую структуру.
Каждую строку Ткее-13ееете можно найти в КВ-13а.ете (с тем отличием, что х1е заменено Т. п11, а вызов Тклхзрелхт — вызовом КВ-Тклхзрьлхт), в выполняются эти строки при одних и тех же условиях. А вот отличия между этими двумя процедурами. Мы поддерживаем узел у в качестве узла, либо удаленного из дерева, либо перемещенного в пределах последнего. В строке 1 у становится указывающим на узел г, если г имеет меньше двух дочерних узлов и, таким образом, оказывается удаленным.
Когда г имеет два дочерних узла, в строке 9 у становится указывающим на узел, следующий в дереве за г, так же, как в процедуре Ткее-(3еьете, и у перемешается в дереве в позицию узла г. Поскольку цвет узла у может измениться, переменная у-отвдзпа1-со1от хранит цвет узла у до любых изменений цвета. В строках 2 и 1О выполняется установка этой переменной немедленно после присваивания значения переменной у. Когда г имеет два дочерних узла, у ф г и узел у перемещается в исходную позицию узла г в красно-черном дереве; строка 20 назначает у тот же цвет, что 358 Часть 111. Структура данньи и цвет узла г, Необходимо хранить исходный цвет у для его проверки в конце процедуры КВ-Редеете; если он был черным, то удаление илн перемещение у может привести к нарушениям свойств красно-черного дерева.
° Как уже говорилось, мы отслеживаем узел х, который перемещается в исходную позицию узла у. Присваивания в строках 4, 7 и 11 делают х указывающим либо на единственный дочерний узел узла у, либо, если у не имеет дочерних узлов, на ограничитель Т. п11. (Вспомним из раздела 12.3, что у узла у нет левого дочернего узла.) ° Поскольку узел х перемещается в исходную позицию узла у, атрибут х.р всегда устанавливается указывающим на исходную позицию родительского по отношению к у узла в дереве, даже если х в действительности является ограничителем Т. пй.
Присваивание атрибуту х.р в строке 6 процедуры КВТкАмзгьАхт имеет место во всех случаях, кроме ситуации, когда з исходно является родителем у (что осуществляется, только когда г имеет два дочерних узла и следующий за з элемент у представляет собой правый дочерний узел з). (Заметим, что когда КВ-ТКАМБРЬАХТ вызывается в строке 5, 8 или 14, третий передаваемый параметр совпадает с х.) Однако если исходным родительским узлом узла у является узел з, нам не нужно, чтобы атрибут к.р указывал на исходный родитель у, поскольку мы удаляем этот узел из дерева. Поскольку узел у передвинется вверх и займет в дереве позицию узла з, установка х. р равным у в строке 13 приведет к тому, что х.р будет указывать на исходную позицию родителя у, даже если х = Т. ти1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
