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

Красно-черными деревьями  называют бинарные деревья поиска, у которых для каждой вершины добавляется дополнительное свойство: вершина является черной или красной. При этом требуется выполнение следующих свойств:

·         корень дерева – черный

·         у каждой красной вершины потомки – черные

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

Для простоты реализации в дерево добавляются фиктивные черные вершины: для каждой вершины дерева, при отсутствии у нее потомка, на место соответствующего потомка вставляется фиктивная черная вершина.

Вершины, отличные от фиктивных, называются внутренними. Будем далее называть листьями вершины, у которых хотя бы один потомок фиктивный. При определении высоты дерева фиктивные вершины учитывать не будем.

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

typedef struct SBTree_

{

 int IsRed;

 int value;

 struct STree_ *par;

 struct STree_ *left, *right;

} SBTree;

здесь указатель par указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Целая переменная IsRed указывает – является ли данная вершина красной. Величина value называется ключом вершины.

 


Отступление на тему языка С. Поля структур.

В вышеприведенном примере кажется весьма накладным использовать целую переменную для хранения всего одного бита информации. Можно попробовать отвести под эту переменную меньше памяти:

typedef struct SBTreeX_

{

 char IsRed;

 int value;

 struct STree_ *par;

 struct STree_ *left, *right;

} SBTreeX;

 

Однако, в силу наличия выравнивания в структурах, для большинства современных машин размеры структур SBTreeX и SBTree окажутся равными.

Можно попробовать `отщипнуть’ один бит для переменной IsRed из целой переменной с ключом данной структуры value. Это можно сделать с помощью полей в структурах. Поля в структурах это – переменные целого типа, при описании которых после имени переменной пишется двоеточие и вслед за ним – количество бит, которые должны быть отведены под данную переменную. Например, в нашем случае, можно определить вершину дерева следующим образом:

typedef struct SBTree1_

{

 unsigned int IsRed :1;

 unsigned int value :31;

 struct STree_ *par;

 struct STree_ *left, *right;

} SBTree1;

 

При этом, следует понимать, что теперь каждая операция с членами структуры IsRed и value будет происходить довольно сложно (имеется реализация данной операции в кодах). Действительно, например, для изменения переменной value ее сначала требуется извлечь из структуры (используя битовые операции), изменить, а затем – поместить обратно.

Следует ожидать, что на IBM-совместимых ЭВМ работа со следующей структурой SBTree2 будет происходить медленнее, чем со структурой SBTree1:

typedef struct SBTree2_

{

unsigned int value :31;

unsigned int IsRed :1;

 struct STree_ *par;

 struct STree_ *left, *right;

} SBTree2;

 

Здесь используется следующий факт: на IBM-совместимых ЭВМ переменные типа int занимают 4 байта и байты располагаются в обратном порядке: от старшего к младшему. Поэтому для извлечения целой переменной из структуры SBTree1 требуется скопировать первые 4 байта структуры в отдельную переменную и обнулить старший бит этой переменной. Для структуры SBTree2 после извлечения первых четырех байт из структуры во внешнюю целую переменную надо еще дополнительно сдвинуть все биты целой переменной вправо на 1 бит.

Простейшие тесты подтверждают данное предположение. Естественно, что разные компиляторы по разному оптимизируют работу с битовыми полями. Так, например, компилятор Microsoft Visual C++ почти нивелирует разницу в скорости работы со всеми описанными типами структур (разница в скорости элементарных операций с данными структурами оценивается примерно 10-20%). Для используемого же компилятора gnu C++  разница в скорости оказалась – вдвое.

Отметим, что данный подход применим далеко не всегда. Поля в структурах обязаны иметь тип unsigned int. В современных версиях языка С  это требование немного ослабло и вместо этого типа часто можно использовать другие целые типы, но, например, тип float все равно использовать нельзя. Пример использованной программы прилагается.

Отступление на тему языка С. Бинарные операции.

В языке С есть возможность стандартной работы с битами, в рамках возможностей, предоставляемых обычными ассемблерами. Для работы с битами используются следующие арифметические операции:

·         арифметическое и:                                        &

·         арифметическое или:                                    |

·         арифметическое не:                                     ~

·         арифметическое исключающее или:          ^

·         сдвиг влево на k разрядов:                           <<k

·         сдвиг вправо на k разрядов:                         >>k

 

 

С помощью этих операций можно осуществить базовые операции с битами:

k-ый бит целого числа i == 0? :                             (i&(1<<k))==0

Положить 1 в k-ый бит целого числа i :             i|=(1<<k)

Положить 0 в k-ый бит целого числа i :             i&=~(1<<k)

Присвоить l-ый бит целого числа j k-тому биту i :

      i = ((j&(1<<l))==0) ? (i&(~(1<<k))) : (i|(1<<k))

 

 

 

 


Высота красно-черного дерева

Наводящим соображением на то, что в красно-черном дереве, состоящем из N вершин, высота h=Q(log2N) ,  является следующий факт: в каждой ветви дерева, начинающейся с корня дерева, не менее половины вершин – черные (т.к., по определению красно-черного дерева, вслед за красной вершиной всегда следует черная и ветвь, начинающаяся с корня дерева, начинается с черной вершины), с другой стороны: в каждой ветви находится равное количество черных вершин (следует заметить, что, тем не менее, в красно-черном дереве черных вершин может быть меньше половины количества всех вершин).

Назовем черной высотой дерева с корневой вершиной r максимальное количество черных вершин во всех ветвях, начинающихся в r и заканчивающихся в листьях, не считая саму вершину r. Будем обозначать ее hb(r).

Заметим, что требование черноты корня красно-черного дерева, вообще говоря, не является обязательным. Действительно, если не использовать это свойство в определении красно-черного дерева, то в таком дереве цвет корня дерева можно заменить с красного на черный с сохранением всех остальных свойств красно-черных деревьев. Будем называть дерево красно-черным’ если из определения красно-черного дерева убрать требование черноты корня. Легко показать, что для красно-черного дерева любое его поддерево является красно-черным’.

Верна следующая

Лемма. В красно-черном дереве с черной высотой hb количество внутренних вершин не менее 2hb+1-1.

Доказательство. Заметим, что смена цвета корня дерева не повлияет на черную высоту дерева. Поэтому данную лемму можно доказать для  красно-черных’ деревьев. Будем доказывать лемму по индукции по высоте красно-черного’ дерева (обычной). Если рассмотреть дерево, состоящее  из одного элемента, то для него лемма верна.

Рассмотрим внутреннюю вершину x. Пусть hb(x)=h. Тогда если ее потомок p - черный, то высота hb(p)=h-1, а если – красный, то hb(p)=h. Т.о., по предположению индукции, в поддеревьях (а они тоже являются красно-черными’ деревьями) содержится не менее 2h-1 вершин, а во всем дереве, соответственно, не менее 2h-1 + 2h-1 + 1=2h+1-1.

¢

Если обычная высота красно-черного дерева равна h, то черная высота дерева будет не меньше h/2-1 и, по лемме, количество внутренних вершин в дереве

N ³ 2h/2-1.

Прологарифмировав неравенство, имеем:

log2 (N+1) ³ h/2

2log2 (N+1) ³  h

h £ 2log2 (N+1)

Итак, учитывая, что для любого бинарного дерева h > log2 N, получаем, что доказана следующая

Теорема.  Для красно-черного дерева, имеющего N внутренних вершин, верна следующая оценка для его высоты

h=Q(log2N),

или, более точно,

log2 N < h £ 2log2 (N+1).

Добавление элемента в красно-черное дерево

 

Новая вершина вставляется в красно-черное дерева в два этапа.

На первом этапе вершина вставляется, как в обычное дерево поиска (без фиктивных вершин). Новая вершина красится в красный цвет. Следует отметить, что, в реальности фиктивных вершин может вообще не быть. Их наличие может обозначаться соответствующими нулевыми указателями у родительских вершин.

Добавление красной вершины x не меняет баланса дерева по черным вершинам.

Т.к. потомки новой вершины – фиктивные, то они – черные, по определению, что соответствует определению красно-черного дерева.

Единственная проблема, которая может возникнуть, это то, что у вставленной красной вершины x может оказаться красный родитель. Требуется изменить дерево, чтобы решить эту проблему.

При преобразованиях дерева мы будем сохранять указанное свойство: у нас будет сохраняться балансировка по черным вершинам и единственная возможная проблема это – некоторая красная вершина x будет иметь красного родителя.

Итак, x->par – красная, то x->par->par – черная (т.к. единственная проблема – нестыковка x->par и x, с другой стороны, у красной вершины может быть только черный родитель).

Будем называть вершину x->par->par->next, где next это – left или right  дядей  вершины x, если x->par->par->next!= x->par.

Рассмотрим все возможные случаи.

0. Если вершина вставляется в пустое дерево, то она просто перекрашивается в черный цвет.

1. У вершины x->par нет родителя, т.е. эта вершина – корневая. В таком случае мы просто перекрашиваем вершину x->par в черный цвет и процесс завершается.

2. Дядя вершины - x красный.

Перекрашиваем родителя, деда и дядю вершины x и рассматриваем в качестве вершины x ее деда: x=x->par->par.

Т.о. мы перенесли проблему выше по ветви дерева.

Осталось рассмотреть случаи, когда дядя вершины x - черный.

 

3. Дядя вершины - x черный, x – левый потомок x->par. Будем в скобках справа от вершины писать черную высоту поддерева (поддерево должно быть красно-черным’), начинающегося с данной вершины. Символами ??? будем обозначать дисбаланс высот (=поддерево не является красно-черным’).

 

В этом случае мы проводим правый поворот x-b-a и в получившемся дереве перекрашиваем две вершины: a и b .

Вершина получившегося дерева – черная, проблем с цветами нет, сохранилась черная высота дерева, начинающегося с корня, баланс черного сохранился. Т.о. дерево сбалансировано. Последующая балансировка не требуется.

4. Дядя вершины - x черный, x – правый потомок x->par.

Делаем левый поворот f-x-b и ситуация сводится к предыдущему случаю. Заметим, что при этом сохранилась черная высота дерева, начинающегося с корня, баланс черного сохранился.

 

 

Все случаи рассмотрены.

 

Итак, после добавления вершины процесс приведения дерева к виду красно-черного дерева сводится к некоторому количеству процедур перекраски 1 (не более h раз, где h – высота дерева) и не более чем к двум поворотам. Причем, после поворотов дерево не требует дальнейших изменений.

Итак, мы доказали следующую теорему

Теорема. Указанный алгоритм позволяет добавлять вершину к красно-черному дереву за время T=O(log2N) операций, где N – количество вершин в дереве.

 

Однопроходное добавление элемента в красно-черное дерево

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

Итак, все, что нам нужно, это – не допустить в процессе поиска элемента, после которого будет вставлен новый элемент, реализации случая 1, т.к. случай 3 сводится к случаю 2, а последний завершает алгоритм. Это можно обеспечить, перекрашивая вершины при поиске листа, после которого следует вставить новую вершину. Иными словами, нам следует обеспечить, чтобы либо у вставляемой вершины был бы черный родитель (тогда ничего больше делать не надо), либо у вставляемой вершины был бы черный дядя (тогда дерево можно сделать красно-черным за один или два поворота).

При поиске листа, после которого следует вставить новую вершину, мы, сначала рассматриваем в качестве текущей вершины p корень дерева. Далее в качестве p рассматриваем один из потомков корня, и т.д. Пусть, для определенности, от вершины p мы переходим к вершине p->left, тогда нам следует обеспечить, чтобы в случае если p->left  была красной, то  p->right должна стать черной вершиной.

Рассмотрим все возможные случаи. Следует рассматривать только случаи, когда оба потомка p красные (легко увидеть, что случаи, когда p->left или p->right – черные нас устраивают).

0. p – корень дерева, оба потомка p – красные. Тогда, все, что нужно сделать – перекрасить обоих потомков p в черный цвет и перейти к рассмотрению следующей вершины p->left.

1. p->parчерный, оба потомка p – красные. Тогда, все, что нужно сделать – перекрасить p и его потомков и перейти к рассмотрению следующей вершины p->left.

 

 

2. p->par – красный, причем p – левый потомок p->par, p->par – левый потомок p->par->par, оба потомка p – красные (случай, когда оба потомка – правые аналогичен) .

Сначала, мы перекрашиваем p и его потомков.  Теперь мы попали в ситуацию, аналогичную случаю 3, рассмотренному выше (заметим, что правый потомок a должен быть черным, что обеспечено на предыдущем шаге прохода). Как было показано выше, за один поворот и одну перекраску проблему можно решить.

3. p->par – красный, причем p – правый потомок p->par, p->par – левый потомок p->par->par, оба потомка p – красные (случай, когда p – левый потомок p->par, p->par – правый потомок p->par->par - аналогичен).

Сначала, мы перекрашиваем p и его потомков.  Теперь мы попали в ситуацию, аналогичную случаю 4, рассмотренному выше. Как было показано выше, за два поворота и одну перекраску проблему можно решить.

На самом деле, стоит отметить некоторую тонкость: несмотря на то, что нашей целью при проходе сверху вниз была ликвидация случая наличия двух красных братьев (после которых вставляется новый элемент!), мы все-равно можем иметь после прохода ситуации двух красных братьев вдоль пройденной ветви (случай 3 при вставке элемента создает именно такую ситуацию!). Предлагается самостоятельно осознать, что это замечание не мешает нам решать поставленную задачу.

 

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

Удаление элемента из красно-черного дерева

Сначала мы удаляем вершину, как в обычном дереве поиска.

Если у удаляемой вершины y всего один внутренний потомок x, то мы просто ставим x на место y. Если вершина y была красной, то проблем не возникает (черная длина дерева не изменяется). Если вершина y – черная, а x – красная, то проблем тоже нет: мы перекрашиваем вершину x, вставшую на место вершины y, в черный цвет и RB-свойства будут выполняться. Наконец, если обе вершины x и y – черные, то нам придется присвоить вершине y двойную черноту. Как с ней бороться – будет ясно далее.

Если у удаляемой вершины y два внутренних потомка w=y->right, z=y->left, то мы извлекаем следующий элемент за y (минимальный в дереве с корнем w) и ставим его на место y.

Теперь все проблемы сместились к вершине, у которой нет внутренних потомков. При ее удалении она становится фиктивной, что не будет противоречить дальнейшему алгоритму. Если данная вершины была красной, то она просто перекрашивается в черный цвет (уже – в качестве фиктивной вершины). Если же она была черной, то ей необходимо приписать двойную черноту.

 

Итак, задача сводится к следующей. Есть вершина в красно-черном дереве x, обладающая двойной чернотой. Все свойства красно-черного дерева выполняются. Требуется привести дерево к такому виду, что в нем все вершины будут просто черными или красными.

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

Рассмотрим различные варианты:

1)брат x – красный;

2-4: брат x – черный:

                     2)потомки брата x – черные;

                     3)правый потомок брата x – черный, левый – красный;

                     4)правый потомок брата x – красный.

 

1)      брат x красный.

 

 

 

 

x остается с двойной чернотой, но получает черного брата. Ситуация сводится к вариантам 2-4.

 

2) брат x – черный, потомки брата x – черные.


Одна чернота x и чернота b переходят к их родителю. Если родитель был красным, то процесс на это завершается. Иначе рассматриваем далее в качестве вершины x вершину a.

 

3) правый потомок брата x – черный, левый – красный.

 

 

Делаем правый поворот c-b-d и перекрашиваем вершины b и c. В результате, получаем, что правый потомок брата x – красный, т.е. приходим к случаю 4.

 

4) правый потомок брата x – красный, левый – не важно.

 

Делаем левый поворот d-b-a  и делаем указанную перекраску (x становится просто черной). При этом цвет корня дерева и вершины c не должны меняться.

Разберемся с балансировкой. Пусть hb(x)=h (не забывать, что в hb(x) не учитывает сама вершина x). То hb(a)=h+2, hb(b)=h+1=hb(d)= количеству черных вершин в любой ветви, начинающейся на c. Отсюда, в результате простой проверки, получаем, что новое дерево является красно-черным.

 

Итак, мы завершили разбор операции удаления вершины в красно-черном дереве.