б. Считая, что bh[Ti] bh[T2], опишите алгоритм со временем работы О (lgra), находящий среди чёрных вершин дерева Т\, имеющих чёрную высоту bh[T2], вершину у с наибольшим ключом.

е. Пусть Ту - поддерево с корнем у. Покажите, как заменить Ту на Ту U {ж} U Т2 за время 0(1) без потери свойства упорядоченности.

г.В какой цвет надо покрасить ж, чтобы сохранить RB-свойства 1, 2 и 4? Объясните, как восстановить свойство 3 за время О (lgra).

д.Убедитесь, что время выполнения процедуры RB-JoiN есть О (lgra).

Замечания

Идея балансировки двоичных деревьев поиска принадлежит Г. М. Адельсону-Вельскому и Е.М.Ландису [2], предложившим в 1962 году класс сбалансированных деревьев, называемых теперь АВЛ-деревьями. Баланс поддерживается с помощью вращений; для его восстановления после добавления или удаления вершины может потребоваться О (lgra) вращений (для дерева с га вершинами). Ещё один класс деревьев поиска, называемых 2-3-деревьями, был предложен Хопкрофтом (J. Е. Hopcroft, не опубликовано) в 1970 году. Здесь баланс поддерживается за счёт изменения степеней вершин. Обобщение 2-3-деревьев, называемое Б-деревьями, предложили Байер и МакКрейт [18]; Б-деревья обсуждаются в главе 19.

Красно-чёрные деревья предложил Байер [17], назвав их «симметричными двоичными Б-деревьями». Гибас и Седжвик [93] подробно изучили их свойства и предложили использовать для наглядности красный и чёрный цвета.

Из многих других вариаций на тему сбалансированных деревьев наиболее любопытны, видимо, «расширяющиеся деревья» (splay trees), которые придумали Слеатор и Тарьян [177]. Эти деревья являются «саморегулирующимися». (Хорошее описание расширяющихся деревьев дал Тарьян [188].) Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого «расширяющие операции» (splay operations), включающие вращения, выполняются при каждом обращении к дереву. Учётная стоимость (amortized cost, гл. 18) в расчёте на одну операцию с деревом для расширяющихся деревьев составляет О (lgra).

15Пополнение структур данных

Далеко не во всех ситуациях можно обойтись лишь классическими структурами данных (двоичными деревьями поиска, двусторонне связанными списками, хеш-таблицами и т.п.) Однако редко требуется придумать что-то совсем новое: в большинстве случаев достаточно расширить какую-либо из классических структур данных, храня вместе с её объектами дополнительную информацию. Эффективное обновление этой информации при выполнении операций иногда требует немалой изобретательности.

В качестве примера в этом разделе рассматриваются красно-чёрные деревья. Храня в вершинах дополнительную информацию, мы сможем быстро находить г-ж по порядку элемент, а также выполнять обратное действие: находить порядковый номер данного элемента множества (разд. 15.1). В разделе 15.2 обсуждается общая схема работы с дополнительной информацией и доказывается теорема, которая облегчает пополнение для красно-чёрных деревьев. В разделе 15.3 эта же теорема используется для построения структуры данных, хранящей динамическое множество промежутков (на числовой прямой) и позволяющей быстро находить элемент множества, перекрывающийся с заданным промежутком.

15.1. Динамические порядковые статистики

Порядковые статистики уже обсуждались в главе 10, где мы искали г-ж по порядку элемент множества из п элементов, что требовало 0(п) операций (если множество предварительно не упорядочено). В данном разделе мы покажем, как с помощью пополненных красно-чёрных деревьев найти г-ж элемент за O(logra) операций. Кроме того, за то же время можно будет найти порядковый номер заданного элемента.

Подходящая структура данных показана на рис. 15.1. Порядковым деревом (order-statistic tree) мы называем красно-чёрное дерево Г, каждая вершина х которого, помимо обычных полей кеу[х], color[x], р[х], left[x] ж right[x] имеет поле size[x]. В нём хранится раз-

мер (количество вершин, не считая NlL-листьев) поддерева с корнем в ж (считая и саму вершину ж). Считая, что в поле вг,ге[шь] записан 0, можно написать такое соотношение:

size[x] = size[left[x]] + size[right[x]] + 1.

(При реализации можно использовать фиктивный элемент nil[T], как в разделе 14.4, а можно каждый раз проверять, не равен ли указатель значению nil, и подставлять 0 вместо значения поля size.)

Поиск г-ro по величине элемента

Мы должны уметь обновлять дополнительную информацию (поля size) при добавлении и удалении элементов. Но сначала объясним, как ею пользоваться. Начнём с поиска г-го элемента. Рекурсивная процедура OS-Select, г) возвращает указатель на г-й элемент поддерева с корнем ж. Найти г-й элемент во всём дереве Г можно с помощью вызова OS-Select (root[T], г).

OS-Select, г)

1г <- вг,ге[/еД[ж]] + 1

2if г = г

3then return ж

4elseif г < г

5then return os-select(/e/t[a:], г)

6else return os-select(ra/7i], г - г)

Этот алгоритм использует ту же идею, что и алгоритмы поиска главы 10. В поддереве с корнем ж сначала идут size[left[x]] вершин левого поддерева, меньших ж, затем сама вершина ж (которая является (вг,ге[/еД[ж]] + 1)-й по счёту), и затем вершины правого поддерева ж.

Процедура начинает с вычисления порядкового номера г вершины ж (строка 1). Если г = г (строка 2), то ж и есть г-й элемент, и мы возвращаем его (строка 3). Если г < г, то искомый элемент находится в левом поддереве вершины ж, и программа рекурсивно вызывает себя (строка 5). Если же г > г, то искомый элемент находится в правом поддереве вершины ж, но его порядковый номер внутри этого поддерева будет уже не г, а г - г. Этот элемент выдаётся при рекурсивном вызове в строке 6.

Покажем, как процедура OS-Select ищет 17-й элемент дерева, изображённого на рис. 15.1. Мы начинаем с корня (с ключом 26), при этом г = 17. Размер левого поддерева корня равен 12, поэтому порядковый номер корня равен 13, и искомая вершина находится в правом поддереве, имея там порядковый номер 17 - 13 = 4. Ищем 4-й элемент поддерева с корнем 41. Левое поддерево вершины 41 имеет размер 5, т.е. порядковый номер вершины 41 равен 6. Ищем