Программа 26: Комбинация рандомизованных BST-деревьев

 

В этой функции принимается рандомизованное решение о том, какой узел использовать в качестве корня объединенного дерева, исходя из равной вероятности размещения корня в любом узле. Приватная функция-член fixN обновляет b->N значением, которое на 1 больше суммы соответствующих полей в поддеревьях (0 для нулевых деревьев).

 

private:

link joinR(link a, link b)

{

if (a == 0) return b;

if (b = 0) return a;

insertR(b, a->item);

b->l = joinR(a->l, b->l);

b->r = joinR(a->r, b->r);

delete a; fixN(b);

return b;

}

public:

void join(ST<Item, Key>& b)

{ int N = head->N;

if (rand ()/(RAND_MAX/(N+b.head->N)+1) < N)

head = joinR(head, b.head);

else head = joinR(b.head, head);

}

 

Аналогично, произвольное решение заменяется рандомизованным в алгоритме remove. Этот метод соответствует нерассмотренному варианту реализации удаления узлов в стандартных BST-деревьях, поскольку он при­водил бы к несбалансированным деревьям.

 

Программа 27: Удаление в рандомизованном BST-дереве.

Мы используем ту же функцию remove, которая применялась для стандартных BST- деревьев, но при этом функция joinLR заменяется функцией, приведенной здесь, которая принимает рандомизованное, а не произвольное ре­шение о замещении удаленного узла предком или потомком, исходя из того, что каждый узел в результирующем дереве с равной вероятностью может быть корнем. Чтобы правильно поддерживать счетчики узлов, в качестве последнего оператора в функции removeR необходимо также включить вызов функции fixN для h.

 

link joinLR (link a, link b)

{

if (a = 0) return b;

if (b - 0) return a;

if (rand()/(RAND_MAX/(a-> N+b ->N)+l)< a-> N)

{ a->r = joinLR(a->r, b);

return a; } else { b->l = joinLR (a, b->l);

return b; }

}

 

Доказательства свойств вероятностных алгоритмов требуют хорошего понимания теории вероятностей, тем не менее, понимание этих доказательств отнюдь не обяза­тельно для программистов, использующих алгоритмы. Осмотрительный программист в любом случае проверит утверждения, подобные лемме 22, не зависимо от того, как они обоснованы (например, убеждаясь в качестве генератора случайных чисел или иных особенностей реализации), и, следовательно, сможет использовать эти ме­тоды со знанием дела. Рандомизованные BST-деревья — вероятно, простейший спо­соб поддержки АТД заполненной таблицы символов при гарантировании почти опти­мальной производительности. Именно поэтому они находят применение во многих практических приложениях.

Красно-черные деревья

Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная) и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом[4].

 

 

9.1 Свойства красно-черных деревьев

 

Красно-черное дерево представляет собой бинарное дерево поиска с одним до­полнительным битом цветав каждом узле. Цвет узла может быть либо красным, либо черным. В соответствии с накладываемыми на узлы дерева ограничениями, ни один путь в красно-черном дереве не отличается от другого по длине более чем в два раза, так что красно-черные деревья являются приближенно сбаланси­рованными[4].

Каждый узел дерева содержит поля color, key, left, rightиp. Если не существу­ет дочернего или родительского узла по отношению к данному, соответствующий указатель принимает значение nil. Мы будем рассматривать эти значения nil как указатели на внешние узлы (листья) бинарного дерева поиска. При этом все “нор­мальные” узлы, содержащие поле ключа, становятся внутренними узлами дерева.

Бинарное дерево поиска является красно-черным деревом, если оно удовле­творяет следующим красно-черным свойствам.

 

1. Каждый узел является красным или черным.

2. Корень дерева является черным.

3. Каждый лист дерева (NIL) является черным.

4. Если узел — красный, то оба его дочерних узла — черные.

5. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов.

 

На рис. 39 показан пример красно-черного дерева. На рисунке черные узлы показаны темным цветом, красные — светлым. Возле каждого узла показана его “черная” высота. У всех листьев она, само собой разумеется, равна 0.

Для удобства работы с красно-черным деревом мы заменим все листья одним ограничивающим узлом, представляющим значение nil. В красно-черном дереве Т ограничитель nil [Т] пред­ставляет собой объект с теми же полями, что и обычный узел дерева. Значение color этого узла равно BLACK (черный), а все остальные поля могут иметь произ­вольные значения.

Использование ограничителя позволяет нам рассматривать дочерний по от­ношению к узлу х NIL как обычный узел, родителем которого является узел х. Хотя можно было бы использовать различные ограничители для каждого значе­ния nil (что позволило бы точно определять их родительские узлы), этот подход привел бы к неоправданному перерасходу памяти. Вместо этого мы используем единственный ограничитель для представления всех nil — как листьев, так и роди­тельского узла корня. Величины полей р, left, rightиkey ограничителя не играют никакой роли, хотя для удобства мы можем присвоить им те или иные значения.

В целом мы ограничим наш интерес к красно-черным деревьям только их внутренними узлами, поскольку только они хранят значения ключей. В остав­шейся части данной главы при изображении красно-черных деревьев все листья опускаются.

Количество черных узлов на пути от узла х (не считая сам узел) к листу будем называть черной высотой узла (black-height) и обозначать как bh (х). В со­ответствии со свойством 5 красно-черных деревьев, черная высота узла — точно определяемое значение. Черной высотой дерева будем считать черную высоту его корня.

Следующая лемма показывает, почему красно-черные деревья хорошо исполь­зовать в качестве деревьев поиска.

Лемма 23: Красно-черное дерево с N внутренними узлами имеет высоту не более чем на

 

 

Рисунок.39. Пример красно-черного дерева

 

 

9.2 Повороты

 

Операции над деревом поиска Tree_Insert и Tree_Delete, будучи приме­нены к красно-черному дереву с N ключами, выполняются за время O( Поскольку они изменяют дерево, в результате их работы могут нарушаться крас­но-черные свойства, перечисленные в предыдущем разделе. Для восстановления этих свойств мы должны изменить цвета некоторых узлов дерева, а также структу­ру его указателей[4].

Изменения в структуре указателей будут выполняться при помощи поворотов (rotations), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска.

При выполнении левого поворота в узле х предполагается, что его правый дочерний узел y не является листом nil[Т]. Левый поворот выполняется “вокруг” связи между хи у, делая у новым корнем поддерева, левым дочерним узлом которого становится ж, а бывший левый потомок узла у — правым потомком х.

В псевдокоде процедуры LEFT_ROTATE предполагается, что right [x] ≠ nil[T], а родитель корневого узла — nil[Т].

Left_Rotate(T, х)

 

1 у ← right[x] > Устанавливаем у.

2 right[x]←left[у] > Левое поддерево y становится правым поддеревом х

3 if left[y] ≠ nil[T]

4 then p[left[y]] ← x

5 p[y] ← p[x] > Перенос родителя x в y

6 if p[x] = nil[T]

7 then root[T] ← у

8 else if x = left[p[x]]

9 then left[p[z]] ← у

10 else right[p[x]] ← у

11 left[y] ← x > x — левый дочерний у

12 p[x] ← у

Код процедуры RIGHT_ROTATE симметричен коду LEFT_ROTATE. Обе эти процедуры выполняются за время 0. При повороте изменяются только указатели, все остальные поля сохраняют своё значение.

 

 

9.3 Вставка

 

Вставка узла в красно-черное дерево с п узлами может быть выполнена за вре­мя О (lgn). Для вставки узла z в дерево Т мы используем немного модифициро­ванную версию процедуры Tree_Insert, которая вставляет узел в дерево, как если бы это было обычное бинарное дерево поиска, а затем окраши­вает его в красный цвет. Для того чтобы вставка сохраняла красно-черные свойства дерева, после нее вызывается вспомогательная процедура RB_Insert_Fixup, кото­рая перекрашивает узлы и выполняет повороты. Вызов RB_Insert (T, z) вставляет в красно-черное дерево Т узел z с заполненным полем key[4]:

RB_Insert (T, z)

1. у ← nil[T]

2. х ← root[T]

3. while x ≠ nil[T]

4. do y ←x

5. if key[z] ← key[x]

6. then x ← left[x]

7. else x ← right[x]

8. p[z] ← у

9. if у = nil[T]

10. then root[T] ← z

11. else if key[z] ← key [y]

12. then left[y] ← z

13. else right[y] ← z

14. Left[z] ← nil[T]gg

15. Right[z] ← nil[T]

16. color [z] ← RED

17. RB_Insert_Fixup(T, z)

Есть четыре отличия процедуры tree_insert от процедуры rb_insert. Во - первых, все NIL в TREE_INSERT заменены на nil[T]. Во-вторых, для поддержки корректности структуры дерева в строках 14-15 процедуры RB_Insert выпол­няется присвоение nil [Т] указателям left [z]иright [z],В третьих, в строке 16 мы назначаем узлу z красный цвет. И наконец, поскольку красный цвет z может вызвать нарушение одного из красно-черных свойств, в строке 17 вызывается вспомогательная процедура RB_Insert_Fixup (T,z), предназначение которой — восстановить красно-черные свойства дерева:

 

 

RB_INSERT_FIXUP (T,z)

1 while color[p[z]] = red

2 do if p[z] = left[p[p[z]]]

3 then у ← right[p[p[z]]]

4 if color [y] = RED

5 then color[p[z]] ← black > Случай 1

6 color [y] ← black > Случай 1

7 color[p[p[z]]] ← RED > Случай 1

8 z ← р[р[г]] > Случай 1

9 else if z ← right [ p [ z]]

10 then z ← p[z] t > Случай 2

11 Left_Rotate (T, z) > Случай 2

12 color[p[z]]] ← BLACK > Случай 3

13 color[p[p[z] ]] ← RED > Случай 3

 

Для того чтобы понять, как работает процедура RB_Insert_Fixup, мы разо­бьем рассмотрение кода на три основные части. Сначала мы определим, какие из красно-черных свойств нарушаются при вставке узла z и окраске его в красный цвет.. После этого мы изучим каждый из трех случаев, которые встречаются в этом цикле, и посмотрим, каким образом достигается цель в каждом случае.

Какие из красно-черных свойств могут быть нарушены перед вызовом RB_INSERT_Fixup. Свойство 1 определённо выполняется, так как оба дочерних узла вставляемого узла являются ограничителями nil[Т]. Свойство 5, согласно которому для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов, также остается в силе, поскольку узел z замещает (черный) ограничитель, будучи при этом красным и имея черные дочерние узлы. Таким образом, может нарушать­ся только свойство 2, которое требует, чтобы корень красно-черного дерева был черным, и свойство 4, согласно которому красный узел не может иметь крас­ного потомка. Оба нарушения возможны в силу того, что узел z после вставки окрашивается в красный цвет. Свойство 2 оказывается нарушенным, если узел z становится корнем, а свойство 4 — если родительский по отношению к 2 узел является красным.

Удаление

Как и остальные базовые операции над красно-черными деревьями с n узлами, удаление узла выполняется за время О (lgn). Удаление оказывается несколько более сложной задачей, чем вставка[4].

Процедура RB_Delete представляет собой немного измененную процедуру Tree_Delete. После удаления узла в ней вызывается вспомога­тельная процедура RB_Delete_Fixup, которая изменяет цвета и выполняет пово­роты для восстановления красно-черных свойств дерева:

RB_Delete(T, z)

1 if left[z] = nil[T] или right[z] = nil[T]

2 then у ←z

3 else у ← Tree_Successor(z)

4 if left[y] ≠ nil[T]

5 then x ← left[y]

6 else x ← right[y]

7 p[x] ← p[y]

8 if p[y] = nil[T]

9 then root[T] ← x

10 else if у = left[p[y]]

11 then left[p[y]] ← x

12 else right[p[y]] ← x

13 if у ≠ z

14 then key[z] ← key[y]

15 Копируем сопутствующие данные у в z

16 if color [у] = BLACK

17 then RB_Delete_Fixup(T, x)

18 return у

 

Имеется три различия между процедурами Tree_Delete и RB_Delete. Во-первых, все ссылки на nil в Tree_Delete заменены в RB_Delete ссылками на ограничитель nil [Т]. Во-вторых, удалена проверка в строке 7 процедуры Tree_Delete (равно ли х nil), и присвоение р[х] ← р [у] выполняется в про­цедуре RB_Delete безусловно. Таким образом, если х является ограничителем nil[T], то его указатель на родителя указывает на родителя извлеченного из дере­ва узла у. В-третьих, в строках 16-17 процедуры RBDelete в случае, если узел y — черный, выполняется вызов вспомогательной процедуры RB_Delete_Fixup. Если узел y — красный, красно-черные свойства при извлечении y из дерева сохраняются в силу следующих причин:

• никакая черная высота в дереве не изменяется;

• никакие красные узлы не становятся соседними;

• так как у не может быть корнем в силу своего цвета, корень остается черным.

Узел х, который передается в качестве параметра во вспомогательную проце­дуру RB_DELETE_FlXUP, является одним из двух узлов: либо это узел, который был единственным потомком у перед извлечением последнего из дерева. В последнем случае безусловное присвоение в строке 7 гарантирует, что родительским по отношению к х узлом становится узел, который ранее был родителем у, независимо от того, является ли хвнутренним узлом с реальным ключом или ограничителем nil[Т].

Теперь мы можем посмотреть, как вспомогательная процедура RB_Insert_ Fixup справляется со своей задачей восстановления красно-черных свойств дерева поиска.

RB_Delete_Fixup(T, х)

1 while х ≠ root[T] и color[x] = black

2 do if х = left[p[x]]

3 then w ← right[p[x]]

4 if color[w] = RED

5 then color [w] ← black >Случай 1

6 color[p[x]]←RED >Случай 1

7 Left_Rotate(T, p[x]) >Случай 1

8 w ← right[p[x]] >Случай1

9 if color[left[w]] = BLACK и color[right[w]] = BLACK

10 then color [w]←REDC >Случай 2

11 x ← p[x] >Случай 2

12 else if color[right[w]] = BLACK

13 then color[left[w]] ← BLACK >Случай 3

14 color [w] ← RED > Случай 3

15 RlGHT_ROTATE(T, w) > Случай 3

16 w ← right[p[x]] > Случай 3

17 color[w] ← color[p[x]] > Случай 4

18 color[p[x]] ← BLACK> Случай 4

19 color [right [w]] <— BLACK > Случай 4

20 Left_Rotate(T, p[x]) > Случай4

21 x ← root[T] > Случай 4

22 else (то же, что и в “then”, с заменой left на right и наоборот)

23 color [х] <— BLACK

 

 

Если извлекаемый из дерева в процедуре RB_Delete узел у чёрный, то мо­гут возникнуть три проблемы. Во-первых, если у был корнем, а теперь корнем стал красный потомок у, нарушается свойство 2. Во-вторых, если и ж, и р [у] (который теперь является также р [x]) были красными, то нарушается свойство 4. И, в-третьих, удаление у приводит к тому, что все пути, проходившие через у, теперь имеют на один чёрный узел меньше. Таким образом, для всех предков у оказывается нарушенным свойство 5. Мы можем исправить ситуацию, утверждая, что узел х — “сверхчерный”, т.е. при рассмотрении любого пути, проходящего через х, добавлять дополнительную 1 к количеству черных узлов. При такой ин­терпретации свойство 5 остается выполняющимся. При извлечении черного узла умы передаем его “черноту” его потомку. Проблема заключается в том, что те­перь узел х не является ни черным, ни красным, что нарушает свойство 1. Вместо этого узел х окрашен либо “дважды черным”, либо “красно-черным” цветом, что дает при подсчете черных узлов на пути, содержащем х, вклад, равный, соответ­ственно, 2 или 1. Атрибут color узла х при этом остается равен либо black (если узел дважды черный), либо red (если узел красно-черный). Другими словами, цвет узла не соответствует его атрибуту color. Процедура RB_Delete_Fixup восстанавливает свойства 1, 2 и 4.

Цель цикла while в строках 1-22 состоит в том, чтобы переместить дополнительную черноту вверх по дереву до тех пор, пока не выполнится одно из перечисленных условий.

 

1. хуказывает на красно-черный узел — в этом случае мы просто делаем узел х“единожды черным” в строке 23.

2. х указывает на корень — в этом случае мы просто убираем излишнюю черноту.

3. Можно выполнить некоторые повороты и перекраску, после которых двой­ная чернота будет устранена.

4. Внутри цикла while х всегда указывает на дважды черную вершину, не яв­ляющуюся корнем. В строке 2 мы определяем, является ли х левым или правым дочерним узлом своего родителя р[х]. Далее приведен подробный код для си­туации, когда х — левый потомок. Для правого потомка код аналогичен и сим­метричен, и скрыт за описанием в строке 22. Указатель wуказывает на второго потомка родителя х. Поскольку узел хдважды черный, узел w не может быть nil[Т] — в противном случае количество черных узлов на пути от р [х] к (едино­жды черному) листу было бы меньше, чем количество черных узлов на пути от р[х] к х.

5. Ключевая идея заключается в необходимости убедиться, что при преобразованиях в каждом случае количество черных узлов (включая дополнительную черноту в х) на пути от корня вклю­чительно до каждого из поддеревьев α, β,..., θ остается неизменным.