RBDeleteFixup()

int System.Data.RBTree< K >.RBDeleteFixup ( int root_id, int x_id, int px_id, int mainTreeNodeID )

inlineprivate

Definition at line 937 of file RBTree.cs.

    {
        if (x_id == 0 && px_id == 0)
        {
            return 0;
        }
        while (((root_id == 0) ? root : root_id) != x_id && color(x_id) == NodeColor.black)
        {
            int num;
            if ((x_id != 0 && x_id == Left(Parent(x_id))) || (x_id == 0 && Left(px_id) == 0))
            {
                num = ((x_id == 0) ? Right(px_id) : Right(Parent(x_id)));
                if (num == 0)
                {
                    throw ExceptionBuilder.InternalRBTreeError(RBTreeError.RBDeleteFixup);
                }
                if (color(num) == NodeColor.red)
                {
                    SetColor(num, NodeColor.black);
                    SetColor(px_id, NodeColor.red);
                    root_id = LeftRotate(root_id, px_id, mainTreeNodeID);
                    num = ((x_id == 0) ? Right(px_id) : Right(Parent(x_id)));
                }
                if (color(Left(num)) == NodeColor.black && color(Right(num)) == NodeColor.black)
                {
                    SetColor(num, NodeColor.red);
                    x_id = px_id;
                    px_id = Parent(px_id);
                    continue;
                }
                if (color(Right(num)) == NodeColor.black)
                {
                    SetColor(Left(num), NodeColor.black);
                    SetColor(num, NodeColor.red);
                    root_id = RightRotate(root_id, num, mainTreeNodeID);
                    num = ((x_id == 0) ? Right(px_id) : Right(Parent(x_id)));
                }
                SetColor(num, color(px_id));
                SetColor(px_id, NodeColor.black);
                SetColor(Right(num), NodeColor.black);
                root_id = LeftRotate(root_id, px_id, mainTreeNodeID);
                x_id = ((root_id == 0) ? root : root_id);
                px_id = Parent(x_id);
                continue;
            }
            num = Left(px_id);
            if (color(num) == NodeColor.red)
            {
                SetColor(num, NodeColor.black);
                if (x_id != 0)
                {
                    SetColor(px_id, NodeColor.red);
                    root_id = RightRotate(root_id, px_id, mainTreeNodeID);
                    num = ((x_id == 0) ? Left(px_id) : Left(Parent(x_id)));
                }
                else
                {
                    SetColor(px_id, NodeColor.red);
                    root_id = RightRotate(root_id, px_id, mainTreeNodeID);
                    num = ((x_id == 0) ? Left(px_id) : Left(Parent(x_id)));
                    if (num == 0)
                    {
                        throw ExceptionBuilder.InternalRBTreeError(RBTreeError.CannotRotateInvalidsuccessorNodeinDelete);
                    }
                }
            }
            if (color(Right(num)) == NodeColor.black && color(Left(num)) == NodeColor.black)
            {
                SetColor(num, NodeColor.red);
                x_id = px_id;
                px_id = Parent(px_id);
                continue;
            }
            if (color(Left(num)) == NodeColor.black)
            {
                SetColor(Right(num), NodeColor.black);
                SetColor(num, NodeColor.red);
                root_id = LeftRotate(root_id, num, mainTreeNodeID);
                num = ((x_id == 0) ? Left(px_id) : Left(Parent(x_id)));
            }
            SetColor(num, color(px_id));
            SetColor(px_id, NodeColor.black);
            SetColor(Left(num), NodeColor.black);
            root_id = RightRotate(root_id, px_id, mainTreeNodeID);
            x_id = ((root_id == 0) ? root : root_id);
            px_id = Parent(x_id);
        }
        SetColor(x_id, NodeColor.black);
        return root_id;
    }

References System.Data.RBTree< K >.color(), System.Data.ExceptionBuilder.InternalRBTreeError(), System.Collections.Generic.Left, System.Data.RBTree< K >.LeftRotate(), System.Data.Parent, System.Data.Right, System.Data.RBTree< K >.RightRotate(), System.Data.RBTree< K >.root, and System.Data.RBTree< K >.SetColor().