Figure 3: _Tree::erase

   iterator erase(iterator _P)
      {if (_Isnil(_P._Mynode()))
         throw out_of_range("invalid map/set<T> iterator");
      _Nodeptr _X, _Xpar;
      _Nodeptr _Y = (_P++)._Mynode();
      _Nodeptr _Z = _Y;
      if (_Isnil(_Left(_Y)))
         _X = _Right(_Y);
      else if (_Isnil(_Right(_Y)))
         _X = _Left(_Y);
      else
         _Y = _Min(_Right(_Y)), _X = _Right(_Y);
      if (_Y == _Z)
         {_Xpar = _Parent(_Z);
         if (!_Isnil(_X))
            _Parent(_X) = _Xpar;
         if (_Root() == _Z)
            _Root() = _X;
         else if (_Left(_Xpar) == _Z)
            _Left(_Xpar) = _X;
         else
            _Right(_Xpar) = _X;
         if (_Lmost() != _Z)
            ;
         else if (_Isnil(_Right(_Z)))
            _Lmost() = _Xpar;
         else
            _Lmost() = _Min(_X);
         if (_Rmost() != _Z)
            ;
         else if (_Isnil(_Left(_Z)))
            _Rmost() = _Xpar;
         else
            _Rmost() = _Max(_X); }
      else
         {_Parent(_Left(_Z)) = _Y;
         _Left(_Y) = _Left(_Z);
         if (_Y == _Right(_Z))
            _Xpar = _Y;
         else
            {_Xpar = _Parent(_Y);
            if (!_Isnil(_X))
               _Parent(_X) = _Xpar;
            _Left(_Xpar) = _X;
            _Right(_Y) = _Right(_Z);
            _Parent(_Right(_Z)) = _Y; }
         if (_Root() == _Z)
            _Root() = _Y;
         else if (_Left(_Parent(_Z)) == _Z)
            _Left(_Parent(_Z)) = _Y;
         else
            _Right(_Parent(_Z)) = _Y;
         _Parent(_Y) = _Parent(_Z);
         std::swap(_Color(_Y), _Color(_Z)); }

   // RECOLOR AND REBALANCE
      if (_Color(_Z) == _Black)
         {for (; _X != _Root() && _Color(_X) == _Black;
            _Xpar = _Parent(_X))
            if (_X == _Left(_Xpar))
               {_Nodeptr _W = _Right(_Xpar);
               if (_Color(_W) == _Red)
                  {_Color(_W) = _Black;
                  _Color(_Xpar) = _Red;
                  _Lrotate(_Xpar);
                  _W = _Right(_Xpar); }
               if (_Isnil(_W))
                  _X = _Xpar;   // shouldn't happen
               else if (_Color(_Left(_W)) == _Black
                  && _Color(_Right(_W)) == _Black)
                  {_Color(_W) = _Red;
                  _X = _Xpar; }
               else
                  {if (_Color(_Right(_W)) == _Black)
                     {_Color(_Left(_W)) = _Black;
                     _Color(_W) = _Red;
                     _Rrotate(_W);
                     _W = _Right(_Xpar); }
                  _Color(_W) = _Color(_Xpar);
                  _Color(_Xpar) = _Black;
                  _Color(_Right(_W)) = _Black;
                  _Lrotate(_Xpar);
                  break; }}
            else
               {_Nodeptr _W = _Left(_Xpar);
               if (_Color(_W) == _Red)
                  {_Color(_W) = _Black;
                  _Color(_Xpar) = _Red;
                  _Rrotate(_Xpar);
                  _W = _Left(_Xpar); }
               if (_Isnil(_W))
                  _X = _Xpar;   // shouldn't happen
               else if (_Color(_Right(_W)) == _Black
                  && _Color(_Left(_W)) == _Black)
                  {_Color(_W) = _Red;
                  _X = _Xpar; }
               else
                  {if (_Color(_Left(_W)) == _Black)
                     {_Color(_Right(_W)) = _Black;
                     _Color(_W) = _Red;
                     _Lrotate(_W);
                     _W = _Left(_Xpar); }
                  _Color(_W) = _Color(_Xpar);
                  _Color(_Xpar) = _Black;
                  _Color(_Left(_W)) = _Black;
                  _Rrotate(_Xpar);
                  break; }}
         _Color(_X) = _Black; }
      _Destval(&_Value(_Z));
      _Freenode(_Z);
      if (0 < _Size)
         --_Size;
      return (_P); }