RBDeleteX()

int System.Data.RBTree< K >.RBDeleteX ( int root_id, int z_id, int mainTreeNodeID )

inlineprivate

Definition at line 759 of file RBTree.cs.

    {
        int num = 0;
        if (Next(z_id) != 0)
        {
            return RBDeleteX(Next(z_id), Next(z_id), z_id);
        }
        bool flag = false;
        int num2 = ((_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX) ? mainTreeNodeID : z_id);
        if (Next(num2) != 0)
        {
            root_id = Next(num2);
        }
        if (SubTreeSize(Next(num2)) == 2)
        {
            flag = true;
        }
        else if (SubTreeSize(Next(num2)) == 1)
        {
            throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidNextSizeInDelete);
        }
        int num3 = ((Left(z_id) != 0 && Right(z_id) != 0) ? Successor(z_id) : z_id);
        num = ((Left(num3) == 0) ? Right(num3) : Left(num3));
        int num4 = Parent(num3);
        if (num != 0)
        {
            SetParent(num, num4);
        }
        if (num4 == 0)
        {
            if (root_id == 0)
            {
                root = num;
            }
            else
            {
                root_id = num;
            }
        }
        else if (num3 == Left(num4))
        {
            SetLeft(num4, num);
        }
        else
        {
            SetRight(num4, num);
        }
        if (num3 != z_id)
        {
            SetKey(z_id, Key(num3));
            SetNext(z_id, Next(num3));
        }
        if (Next(num2) != 0)
        {
            if (root_id == 0 && z_id != num2)
            {
                throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinDelete);
            }
            if (root_id != 0)
            {
                SetNext(num2, root_id);
                SetKey(num2, Key(root_id));
            }
        }
        for (int num5 = num4; num5 != 0; num5 = Parent(num5))
        {
            RecomputeSize(num5);
        }
        if (root_id != 0)
        {
            for (int num6 = num2; num6 != 0; num6 = Parent(num6))
            {
                DecreaseSize(num6);
            }
        }
        if (color(num3) == NodeColor.black)
        {
            root_id = RBDeleteFixup(root_id, num, num4, mainTreeNodeID);
        }
        if (flag)
        {
            if (num2 == 0 || SubTreeSize(Next(num2)) != 1)
            {
                throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidNodeSizeinDelete);
            }
            _inUseSatelliteTreeCount--;
            int num7 = Next(num2);
            SetLeft(num7, Left(num2));
            SetRight(num7, Right(num2));
            SetSubTreeSize(num7, SubTreeSize(num2));
            SetColor(num7, color(num2));
            if (Parent(num2) != 0)
            {
                SetParent(num7, Parent(num2));
                if (Left(Parent(num2)) == num2)
                {
                    SetLeft(Parent(num2), num7);
                }
                else
                {
                    SetRight(Parent(num2), num7);
                }
            }
            if (Left(num2) != 0)
            {
                SetParent(Left(num2), num7);
            }
            if (Right(num2) != 0)
            {
                SetParent(Right(num2), num7);
            }
            if (root == num2)
            {
                root = num7;
            }
            FreeNode(num2);
            num2 = 0;
        }
        else if (Next(num2) != 0)
        {
            if (root_id == 0 && z_id != num2)
            {
                throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinEndDelete);
            }
            if (root_id != 0)
            {
                SetNext(num2, root_id);
                SetKey(num2, Key(root_id));
            }
        }
        if (num3 != z_id)
        {
            SetLeft(num3, Left(z_id));
            SetRight(num3, Right(z_id));
            SetColor(num3, color(z_id));
            SetSubTreeSize(num3, SubTreeSize(z_id));
            if (Parent(z_id) != 0)
            {
                SetParent(num3, Parent(z_id));
                if (Left(Parent(z_id)) == z_id)
                {
                    SetLeft(Parent(z_id), num3);
                }
                else
                {
                    SetRight(Parent(z_id), num3);
                }
            }
            else
            {
                SetParent(num3, 0);
            }
            if (Left(z_id) != 0)
            {
                SetParent(Left(z_id), num3);
            }
            if (Right(z_id) != 0)
            {
                SetParent(Right(z_id), num3);
            }
            if (root == z_id)
            {
                root = num3;
            }
            else if (root_id == z_id)
            {
                root_id = num3;
            }
            if (num2 != 0 && Next(num2) == z_id)
            {
                SetNext(num2, num3);
            }
        }
        FreeNode(z_id);
        _version++;
        return z_id;
    }

References System.Data.RBTree< K >._accessMethod, System.Data.RBTree< K >._inUseSatelliteTreeCount, System.Data.RBTree< K >._version, System.Data.RBTree< K >.color(), System.Data.RBTree< K >.DecreaseSize(), System.Data.RBTree< K >.FreeNode(), System.Data.ExceptionBuilder.InternalRBTreeError(), System.Data.RBTree< K >.Key(), System.Collections.Generic.Left, System.Data.RBTree< K >.Next(), System.Data.Parent, System.Data.RBDeleteFixup, System.Data.RBTree< K >.RBDeleteX(), System.Data.RBTree< K >.RecomputeSize(), System.Data.Right, System.Data.RBTree< K >.root, System.Data.RBTree< K >.SetColor(), System.Data.RBTree< K >.SetKey(), System.Data.RBTree< K >.SetLeft(), System.Data.RBTree< K >.SetNext(), System.Data.RBTree< K >.SetParent(), System.Data.RBTree< K >.SetRight(), System.Data.RBTree< K >.SetSubTreeSize(), System.Data.RBTree< K >.SubTreeSize(), and System.Data.RBTree< K >.Successor().

Referenced by System.Data.RBTree< K >.DeleteByIndex(), System.Data.RBTree< K >.RBDelete(), and System.Data.RBTree< K >.RBDeleteX().