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

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

Если у удаляемой вершины 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. Отсюда, в результате простой проверки, получаем, что новое дерево является красно-черным.

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

Лекция 11

B-деревья

До сих пор мы рассматривали только бинарные деревья. Теперь рассмотрим деревья, имеющие большую степень ветвления. При этом хочется, чтобы сохранялись свойства, аналогичные свойству сбалансированности в сбалансированных деревьях. Этим условиям удовлетворяют B-деревья. Отметим, что B-деревья являются основным инструментом построения многих современных файловых систем (RaiserFS, JFS, XFS).

В B-деревьях в каждой вершине может содержаться несколько элементов (ключей). Высота дерева определяется как максимальное количество вершин в ветвях. Будем далее рассматривать случай, когда все элементы (ключи) в дереве различны.

В-дерево степени n определяется следующим образом

· каждая вершина дерева, кроме корня, содержит от n-1 до 2n-1 элемента (ключей) и от n до 2n ссылок на дочерние элементы; корень дерева содержит не более 2n-1 элементов (ключей) и не более 2n ссылок на дочерние элементы

· В-дерево идеально сбалансировано, более того, длины всех ветвей совпадают;

· элементы в каждой вершине упорядочены по возрастанию

· если в вершине содержится k элементов, то в ней содержится k+1 ссылок на дочерние вершины (кроме листьев, ссылок на дочерние вершины не содержащих);

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

· все элементы x_i в поддереве V, ссылка на который расположена после некоторого элемента y больше y; все элементы x_j в поддереве V, ссылка на который расположена до некоторого элемента z больше z.

Пример В-дерева степени 3:

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

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

#define NB 100

---

Дата добавления: 2015-10-30