DadsType : TtdChildType;
IsBalanced : boolean;
begin
{вставить новый элемент, вернуться к вставленному узлу и его связям с родительским узлом}
Node := bstInsertPrim(aItem, OurType);
{окрасить его в красный цвет}
Node^.btColor := rbRed;
{продолжать применение в цикле алгоритмов балансировки при вставке в красно-черное дерево до тех пор, пока дерево не окажется сбалансированным}
repeat
{предположим, что дерево сбалансировано}
IsBalanced :=true;
{если узел является корневым, задача выполнена и дерево сбалансировано, поэтому будем считать, что мы находимся не в корневом узле}
if (Node <> FBinTree.Root) then begin
{поскольку мы находимся не в корневом узле, необходимо получить родительский узел данного узла}
Dad := Node^.btParent;
{если родительский узел черный, задача выполнена и дерево сбалансировано, поэтому будем считать, что родительский узел красный}
if (Dad^.btColor = rbRed) then begin
{если родительский узел является корневым, достаточно перекрасить его в черный цвет, и задача будет выполнена}
if (Dad = FBinTree.Root) then
Dad^.btColor := rbBlack {в противном случае родительский узел, в свою очередь, имеет родительский узел}
else begin
{получить прародительский узел (он должен быть черным) и перекрасить его в красный цвет}
Grandad := Dad^.btParent;
Grandad^.btColor := rbRed;
{получить узел, соответствующий понятию дяди}
if (Grandad^.btChild[ctLeft] = Dad) then begin
DadsType := ctLeft;
Uncle := Grandad^.btChild[ ctRight ];
end
else begin
DadsType := ctRight;
Uncle := Grandad^.btChild[ ctLeft ];
end;
{если дядя тоже имеет красный цвет (обратите внимание, что он может быть нулевым!), окрасить родительский узел в черный цвет, дядю в черный цвет и повторить процесс, начиная с прародительского узла}
if IsRed(Uncle) then begin
Dad^.btColor :=rbBlack;
Uncle^.btColor := rbBlack;
Node := Grandad;
IsBalanced := false;
end
{в противном случае дядя окрашен в черный цвет?}
else begin
{если текущий узел имеет такие же отношения со своим родительским узлом, какие его родительский узел имеет с прародительским (т.е. они оба являются либо левыми, либо правыми дочерними узлами), нужно окрасить родительский узел в черный цвет и повысить его ранг. Задача выполнена}
OurType := GetChildType(Node);
if (OurType = DadsType) then begin
Dad^.btColor := rbBlack;
rbtPromote(Dad);
end
{в противном случае необходимо окрасить узел в черный цвет и повысить его ранг посредством применения спаренного двустороннего поворота; задача выполнена}