Красно черное дерево удаление элемента

Красно-чёрное дерево (удалить)

Доказательство: Докажем по индукции. При [math]h=1[/math] получаем дерево, в котором чёрными являются только листья, а их больше одного. Иначе пусть корень — чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем [math]2^[/math] элементов. Тогда всё дерево имеет более [math]2^[/math] элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту [math]h[/math] , то есть, как только что было показано, не менее [math]2^[/math] элементов. Таким образом, дерево будет иметь более [math]2^[/math] элементов.

Доказательство: Возьмём самый длинный путь в дереве. Всего в нём [math]h+1[/math] узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше [math](h-1)/2[/math] , и, по первому утверждению, [math]2^[/math] элементов.

Отсюда также получаем, что высота дерева не более [math]2log_2 N+1[/math] , где N — число элементов дерева, т.е. [math]O(log N)[/math]

Операции

• Вставка элемента. Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын — лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:

1. «Дядя» этого узла тоже красный. Тогда просто перекрашиваем «отца» и «дядю» в чёрный цвет, а «деда» — в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.

2. «Дядя» чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.

• Удаление вершины.При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

1. Если у вершины нет детей, то изменяем указатель на неё у родителя на nil.
2. Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
3. Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

Проверим балансировку дерева. Т.к. при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца — в красный цвет.

2. Если брат текущей вершины был чёрным, то получаем три случая:

• Если у брата правый ребёнок чёрный,а левый красный, то перекрашиваем брата и его левого сына и делаем вращение.

• В же у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца — в чёрный, делаем вращение и выходим из алгоритма.

Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева. При удалении выполняется не более трёх вращений.

• Объединение красно-чёрных деревьев. Объединение двух красно-чёрных деревьев [math]T_[/math] и [math]T_[/math] по элементу x выполняется, когда [math]key[T_] \leqslant x[/math] и [math]x \leqslant key[T_][/math] .

Найдём чёрные высоты деревьев. Предположим также, что [math]bh[T_] \geqslant bh[T_][/math] . Тогда в дереве [math]T_[/math] ищем среди чёрных вершин, имеющих чёрную высоту [math]bh[T_][/math] , вершину y с наибольшим ключом. Пусть [math]T_[/math] — поддерево с корнем y. Объединяем это дерево с [math]T_[/math] в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.

Т.к. общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за [math]O(\log)[/math] .

Источник

Вопрос 12: Красно-чёрное дерево: балансировка при вставке и удалении

Красно-чёрное дерево — двоичное дерево поиска, в котором баланс осуществляется на основе «цвета» узла дерева, который принимает только два значения: «красный» и «чёрный».

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

Узлы красятся в один из двух цветов. Если узел — красный, его сыновья — обязательно чёрные. Вставляемый узел — всегда красный. При появлении цепочки из двух красных узлов, дерево перестраивается. Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для которого выполняются следующие свойства:

1. Каждый узел промаркирован красным или чёрным цветом
2. Корень и конечные узлы (листья) дерева — чёрные
3. У красного узла родительский узел — черный
4. Все простые пути из любого узла х до листьев содержат одинокавое количества чёрных узлов
5. Чёрный узел может иметь чёрного родителя

Теорема (не уверена, что она нужна, но пусть будет): красно-чёрное дерево с N ключами имеет высоту h = O(log N).

Реализация

Вставка элемента

Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil (то есть этот сын — лист). Вставляем вместо него новый элемент с nil -потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство 3, для исправления достаточно рассмотреть два случая:

1. «Дядя» этого узла тоже красный. Тогда, чтобы сохранить свойства 3 и 4, просто перекрашиваем «отца» и «дядю» в чёрный цвет, а «деда» — в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин «отцы» черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству 2.
2. «Дядя» чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство 3 и постоянство черной высоты сохраняются.

Удаление вершины

При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

1. Если у вершины нет детей, то изменяем указатель на неё у родителя на nil.
2. Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
3. Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины:

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца — в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас x имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.
2. Если брат текущей вершины был чёрным, то получаем три случая:
   • Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через b, но добавит один к числу чёрных узлов на путях, проходящих через x, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
   • Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у х есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни х, ни его отец не влияют на эту трансформацию.
   • Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца — в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство 3 и 4 не нарушаются. Но у х теперь появился дополнительный чёрный предок: либо а стал чёрным, или он и был чёрным и b был добавлен в качестве чёрного дедушки. Таким образом, проходящие через x пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.

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

Вставка в RB-деревья бинарного поиска

private: int red (link x) < if (x==0) return 0; return x->red;> void RBinsert(link& h, Item x, int sw) < if(h==0) < h= new node(x); return; > if (red(h->1) && red(h->r)) < h->red=1; h->1->red=0; h->r->red=0; > if (x.key()< h->item.key()) < RBinsert(h->1, x, 0); if (red(h) && red(h->1) && sw) rotR(h); if (red(h->1) && red(h->1->1)) < rotR(h); h->red=0; h->r_.red=1; > > else < RBinsert(h->r, x, 1); if (red(h) && red(h->r) && !sw) rotL(h); if (red(h->r) && red(h->r->r)) < rotL(h); h->red=0; h->1->red=1; > > > public: void insert(Item x) < RBinsert (head, x, 0); head->red=0; > 

Источник