Рисунок 8.15. Балансировка после удаления: заключительный случай
Итак, мы рассмотрели все возможности. При этом использовались два рекурсивных шага или, точнее, два шага, которые требовали дальнейших усилий по балансировке. Первый - когда братский узел был красным, и его нужно было сделать черным. Второй - когда родительский, братский и узлы-племянники были черными. Существовали еще три случая: родительский узел был красным, а братский узел и узлы-племянники были черными;
братский узел был черным, а дальний узел-племянник красным (цвет родительского узла и ближайшего узла-племянника "не имели значения");
и, наконец, случай, когда братский узел был черным, дальний узел-племянник черным, а ближайший узел-племянник красным. Если вы еще раз взглянете на рисунки 8.12, 8.13, 8.14 и 8.15, то убедитесь, что мы рассмотрели все варианты.
Опуская математические выкладки, отметим, что алгоритм удаления из красно-черного дерева является алгоритмом типа O(log(n)), хотя постоянный коэффициент времени больше, чем в случае простого бинарного дерева.
Операция удаления узла из красно-черного дерева реализуется с помощью кода, представленного в листинге 8.25.
Листинг 8.25. Удаление из красно-черного дерева
procedure TtdRedBlackTree.Delete(aItem : pointer);
var
Node : PtdBinTreeNode;
Dad : PtdBinTreeNode;
Child : PtdBinTreeNode;
Brother : PtdBinTreeNode;
FarNephew : PtdBinTreeNode;
NearNephew : PtdBinTreeNode;
IsBalanced : boolean;
ChildType : TtdChildType;
begin
{выполнить поиск узла, который нужно удалить; этот узел будет иметь единственный дочерний узел}
Node := bstFindNodeToDelete(aItem);
{если узел красный или является корневым, его можно безнаказанно удалить}
if (Node^.btColor = rbRed) or (Node = FBinTree.Root) then begin
FBinTree.Delete(Node);
dec(FCount);
Exit;
end;
{если единственный дочерний узел является красным, перекрасить его в черный цвет и удалить узел}
if (Node^.btChild[ctLeft] =nil) then
Child := Node^.btChild[ctRight] else
Child :=Node^.btChild[ctLeft];
if IsRed(Child) then begin
Child^.btColor :=rbBlack;
FBinTree.Delete(Node);
dec(FCount);
Exit;
end;
{на этом этапе узел, который нужно удалить, - узел Node; он является черным и известно, что дочерний узел Child, который его заменит, является черным (а также может быть нулевым!) и что существует родительский узел узла Node (который вскоре станет родительским узлом узла Child); братский узел узла Node также существует в соответствии с правилом, сформулированным для черных узлов}
{если узел Child является нулевым, необходимо несколько упростить выполнение цикла и определить родительский и братский узлы и определить, является ли узел Node левым дочерним узлом}
if (Child = nil) then begin
Dad := Node^.btParent;
if (Node = Dad^.btChild[ctLeft]) then begin
ChildType :=ctLeft;
Brother := Dad^.btChild[ctRight];
end
else begin
ChildType :=ctRight;
Brother := Dad^.btChild[ctLeft];
end;
end
else begin
{следующие три строки предназначены просто для введения в заблуждение компилятора и предотвращения вывода ряда ложных предупреждений}
Dad := nil;
Brother := nil;
ChildType :=ctLeft;
end;
{удалить узел — он больше не нужен}
FBinTree.Delete(Node);
dec(FCount);
Node := Child;
{циклически применять алгоритмы балансировки при удалении из красно-черного дерева до тех пор, пока дерево не окажется сбалансированным}
repeat
{предположим, что дерево сбалансировано}
IsBalanced := true;
{если узел является корневым, балансировка выполнена, поэтому предположим, что это не так}
if (Node <> FBinTree.Root) then begin
{получить родительский и братский узлы}
if (Node <> nil) then begin
Dad := Node^.btParent;
if (Node = Dad^.btChild[ctLeft]) then begin
ChildType := ctLeft;
Brother := Dad^.btChild[ctRight];
end
else begin
ChildType := ctRight;
Brother := Dad^.btChild[ctLeft];
end;
end;
{нам требуется наличие черного братского узла, поэтому если в настоящий момент братский узел окрашен в красный цвет, окрасить родительский узел в красный цвет, братский узел в черный цвет и повысить ранг братского узла; затем снова повторить цикл}
if (Brother^.btColor = rbRed) then begin
Dad^.btColor := rbRed;
Brother^.btColor :=rbBlack;
rbtPromote(Brother);
IsBalanced := false;
end
{ в противном случае братский узел является черным}
else begin
{получить узлы-племянники, помеченные как дальний и ближний}
if (ChildType = ctLeft) then begin
FarNephew := Brother^.btChild[ctRight];
NearNephew := Brother^.btChild[ctLeft];
end
else begin
FarNephew := Brother^.btChild[ctLeft];
NearNephew := Brother^.btChild[ctRight];
end;
{если дальний узел-племянник является красным (обратите внимание, что он может быть нулевым), окрасить его в черный цвет, братский узел в цвет родительского узла, а родительский узел в красный цвет, а затем повысить ранг братского узла; задача выполнена}
if IsRed( FarNephew) then begin
FarNephew^.btColor :=rbBlack;
Brother^.btColor := Dad^.btColor;
Dad^.btColor :=rbBlack;
rbtPromote(Brother);
end
{в противном случае дальний узел-племянник является черным}
else begin
{если ближний узел-племянник является красным (обратите внимание, что он может быть нулевым), окрасить его в цвет родительского узла, родительский узел в черный цвет и повысить ранг узла-племянника посредством спаренного двустороннего поворота; в этом случае задача выполнена}
if isRed(NearNephew) then begin
NearNephew^.btColor := Dad^.btColor;
Dad^.btColor :=rbBlack;
rbtPromote(rbtPromote(NearNephew));
end
{в противном случае ближний узел-племянник является также черным}
else begin
{если родительский узел красный, окрасить его в черный цвет, а братский узел в красный, в результате чего задача будет выполнена}
if (Dad^.btColor = rbRed) then begin
Dad^.btColor :=rbBlack;
Brother^.btColor := rbRed;
end
{в противном случае родительский узел красный: окрасить братский узел в красный цвет и начать балансировку с родительского узла}
else begin
Brother^.btColor := rbRed;
Node := Dad;
IsBalanced := false;
end;
end;
end;
end;
end;
until IsBalanced;
end;
За исключением перекрытых методов Insert и Delete, класс TtdRedBlackTree не представляет особого интереса. Код интерфейса и дополнительного внутреннего метода, выполняющего повышение ранга узла, приведен в листинге 8.26.
Листинг 8.26. Класс TtdRedBlack и метод повышения ранга узла
type
TtdRedBlackTree = class(TtdBinarySearchTree) private protected
function rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;
public
procedure Delete(aItem : pointer); override;
procedure Insert(aItem : pointer); override;
end;
function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;
var
Parent : PtdBinTreeNode;
begin
{пометить родительский узел узла, ранг которого повышается}
Parent := aNode^.btParent;
{в обоих случаях существует 6 связей, которые необходимо разорвать и перестроить: связь узла с его дочерним узлом и противоположная связь; связь узла с его родительским узлом и противоположная связь; и связь родительского узла с его родительским узлом и противоположная связь; обратите внимание, что дочерний узел данного узла может быть нулевым}
{повысить ранг левого дочернего узла, т.е. выполнить поворот родительского узла вправо}
if (Parent^.btChild[ctLeft] = aNode) then begin
Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];
if (Parent^.btChild[ctLeft]<> nil) then
Parent^.btChild[ctLeft]^.btParent := Parent;
aNode^.btParent := Parent^.btParent;
if (aNode^.btParent^.btChild[ctLeft] = Parent) then
aNode^.btParent^.btChild[ctLeft] := anode
else
aNode^.btParent^.btChild[ctRight J := aNode;
aNode^.btChild[ctRight] := Parent;
Parent^.btParent := aNode;
end
{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}
else begin
Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];
if (Parent^.btChild[ctRight]<> nil) then
Parent^.btChild[ctRight]^.btParent := Parent;
aNode^.btParent := Parent^.btParent;
if (aNode^.btParent^.btChild[ctLeft] = Parent) then
aNode^.btParent^.btChild[ctLeft] := anode else
aNode^.btParent^.btChild[ctRight] := aNode;
aNode^.btChild[ctLeft] := Parent;
Parent^.btParent := aNode;
end;
{вернуть узел, ранг которого был повышен}
Result := aNode;
end;
Исходный код класса TtdRedBlackTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.
В этой главе мы рассмотрели бинарные деревья - важную структуру данных, которая может использоваться во многих прикладных приложениях. Мы рассмотрели стандартное бинарное дерево, а затем перешли к исследованию его сортированной разновидности - дереву бинарного поиска.
В ходе рассмотрения дерева бинарного поиска мы ознакомились с проблемой, которая может возникнуть во время вставки и удаления - проблемой вырождения дерева, - именно в это связи мы исследовали способы ее устранения. Первое решение, скошенное дерево, предоставляет хорошую возможность, несмотря на то, что при этом эффективность вставки и удаления лишь в среднем, а не всегда, описывается соотношением O(log(n)). Однако эта разновидность дерева представляет собой приемлемый компромисс между стандартным деревом бинарного поиска и таким действительно сбалансированным деревом, как красно-черное дерево.
Воспользовавшись красно-черным деревом, мы, наконец, получили полное дерево бинарного поиска, имеющее встроенные алгоритмы балансировки как для вставки, так и для удаления.
Глава 9. Очереди по приоритету и пирамидальная сортировка.
В главе 3 мы рассмотрели несколько очень простых структур данных. Одной из них была очередь. В эту структуру можно было добавлять элементы, а затем извлекать их в порядке поступления. При этом сохранение даты и времени создания записи позволяло не обращать внимания на реальную длину элемента в очереди. Вместо этого мы просто организовали элементы по порядку их поступления в связный список или массив, а затем удаляли их в порядке поступления. При этом использовались две базовые операции: "добавление элемента в очередь" (называемая еще постановкой в очередь) и "удаление самого старого элемента очереди" (или вывод из очереди).
