Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deRedBlack.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deRedBlack.hpp
    00003 ///
    00004 /// @brief templated red-black tree
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Apr 2003
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DEREDBLACK_HPP
    00029 #define DEREDBLACK_HPP
    00030
    00031 #include "deList.hpp"
    00032
    00033 // part of this code is adapted from a Java applet demo which can be found at
    00034 // http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html
    00035
    00036 template <class T>
    00037 class deTRedBlack
    00038 {
    00039     class TRBNode
    00040     {
    00041     public:
    00042         explicit TRBNode()
    00043             :Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
    00044         {
    00045         }
    00046         TRBNode(const T & ref)
    00047             :Data(ref), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
    00048         {
    00049         }
    00050         TRBNode(const TRBNode & ref)
    00051             :Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
    00052         {
    00053         }
    00054         ~TRBNode()
    00055             {}
    00056         bool operator ==(const T & ref)
    00057         {
    00058             return Data == ref;
    00059         }
    00060         bool operator >(const T & ref)
    00061         {
    00062             return Data > ref;
    00063         }
    00064         bool operator <(const T & ref)
    00065         {
    00066             return Data < ref;
    00067         }
    00068         void CopyPtrs(const TRBNode * ref)
    00069         {
    00070             Left = ref->Left;
    00071             Right = ref->Right;
    00072             Parent = ref->Parent;
    00073             Color = ref->Color;
    00074         }
    00075         template<class _Ty> inline
    00076         void Swap(_Ty& _X, _Ty& _Y)
    00077         {
    00078             _Ty _Tmp(_X);
    00079             _X = _Y;
    00080             _Y = _Tmp;
    00081         }
    00082         void SwapWith(TRBNode * Swapper, TRBNode* &Root)
    00083         {
    00084             if (Left)
    00085                 Left->Parent = Swapper;
    00086             if (Right)
    00087                 Right->Parent = Swapper;
    00088             if (Swapper->Left)
    00089                 Swapper->Left->Parent = this;
    00090             if (Swapper->Right)
    00091                 Swapper->Right->Parent = this;
    00092             if (Parent)
    00093             {
    00094                 if (Parent->Left == this)
    00095                 {
    00096                     Parent->Left = Swapper;
    00097                 }
    00098                 else if (Parent->Right == this)
    00099                 {
    00100                     Parent->Right = Swapper;
    00101                 }
    00102                 else if (Swapper->Right == this)
    00103                 {
    00104                     Swapper->Right = Swapper;
    00105                 }
    00106                 else if (Swapper->Left == this)
    00107                 {
    00108                     Swapper->Left = Swapper;
    00109                 }
    00110             }
    00111             else
    00112                 Root = Swapper;
    00113             if (Swapper->Parent)
    00114             {
    00115                 if (Swapper->Parent->Left == Swapper)
    00116                 {
    00117                     Swapper->Parent->Left = this;
    00118                 }
    00119                 else if (Swapper->Parent->Right == Swapper)
    00120                 {
    00121                     Swapper->Parent->Right = this;
    00122                 }
    00123                 else if (Right == Swapper)
    00124                 {
    00125                     Right = this;
    00126                 }
    00127                 else if (Left == Swapper)
    00128                 {
    00129                     Left = this;
    00130                 }
    00131             }
    00132             else
    00133                 Root = this;
    00134             Swap(Left, Swapper->Left);
    00135             Swap(Right, Swapper->Right);
    00136             Swap(Parent, Swapper->Parent);
    00137             Swap(Color, Swapper->Color);
    00138         }
    00139         void Destroy()
    00140         {
    00141             if (Left)
    00142                 Left->Destroy();
    00143             if (Right)
    00144                 Right->Destroy();
    00145             delete this;
    00146         }
    00147         void AddDataToList(deTList <T*> &list)
    00148         {
    00149             list.AddElement(&Data);
    00150             if (Left)
    00151                 Left->AddDataToList(list);
    00152             if (Right)
    00153                 Right->AddDataToList(list);
    00154         }
    00155
    00156         TRBNode *Left, *Right;
    00157         TRBNode *Parent;
    00158         enum Color_t {Red, Black} Color;
    00159         deTRedBlack * Tree;
    00160         T Data;
    00161     };
    00162
    00163 private:
    00164     TRBNode * m_Root;
    00165     long m_Length;
    00166
    00167 public:
    00168     deTRedBlack()
    00169     {
    00170         m_Root = NULL;
    00171         m_Length = 0;
    00172     }
    00173     ~deTRedBlack()
    00174     {
    00175         EmptyTree();
    00176     }
    00177
    00178     void EmptyTree()
    00179     {
    00180         if (m_Root)
    00181             m_Root->Destroy();
    00182         m_Root = NULL;
    00183         m_Length = 0;
    00184     }
    00185
    00186     void* FindValue(const T& Val, T* &obj) const
    00187     {
    00188         TRBNode *Node = m_Root;
    00189         while (Node)
    00190         {
    00191             if (*Node == Val)
    00192                 break;
    00193             if (*Node > Val)
    00194                 Node = Node->Left;
    00195             else
    00196                 Node = Node->Right;
    00197         }
    00198         if (!Node)
    00199         {
    00200             obj = NULL;
    00201             return NULL;
    00202         }
    00203         else
    00204             obj = &(Node->Data);
    00205         return Node;
    00206     }
    00207     void* FindValue(const T& Val, T & obj) const
    00208     {
    00209         T * objptr;
    00210         void * ptr;
    00211         ptr = FindValue(Val, objptr);
    00212         if (objptr)
    00213             obj = *objptr;
    00214         return ptr;
    00215     }
    00216     void* GetRoot(T* &obj) const
    00217     {
    00218         TRBNode *Node = m_Root;
    00219         obj = NULL;
    00220         if (!Node)
    00221         {
    00222             return NULL;
    00223         }
    00224         obj = &(Node->Data);
    00225         return Node;
    00226     }
    00227     void * GetLeftMost(T &obj)
    00228     {
    00229         T * objptr;
    00230         void * ptr;
    00231         ptr = GetLeftMost(objptr);
    00232         if (objptr)
    00233             obj = *objptr;
    00234         return ptr;
    00235     }
    00236     void * GetLeftMost(T* &obj)
    00237     {
    00238         TRBNode *Node = m_Root;
    00239         obj = NULL;
    00240         if (!Node)
    00241         {
    00242             return NULL;
    00243         }
    00244         while (Node->Left)
    00245             Node = Node->Left;
    00246         if (Node)
    00247         {
    00248             obj = &(Node->Data);
    00249         }
    00250         return Node;
    00251     }
    00252     void * GetLeftMostLeaf(T* &obj)
    00253     {
    00254         TRBNode *Node = m_Root;
    00255         obj = NULL;
    00256         if (!Node)
    00257         {
    00258             return NULL;
    00259         }
    00260         while (Node->Left || Node->Right)
    00261         {
    00262             if (Node->Left)
    00263                 Node = Node->Left;
    00264             Node = Node->Right;
    00265         }
    00266         if (Node)
    00267         {
    00268             obj = &(Node->Data);
    00269         }
    00270         return Node;
    00271     }
    00272     void * GetNextRight(void * current, T &obj)
    00273     {
    00274         T * objptr;
    00275         void * ptr;
    00276         ptr = GetNextRight(current, objptr);
    00277         if (objptr)
    00278             obj = *objptr;
    00279         return ptr;
    00280     }
    00281     void * GetNextRight(void * current, T* &obj)
    00282     {
    00283         TRBNode *Node = (TRBNode*)current;
    00284         obj = NULL;
    00285         if (!Node)
    00286         {
    00287             return NULL;
    00288         }
    00289         if (Node->Right)
    00290         {
    00291             Node = Node->Right;
    00292             while (Node->Left)
    00293                 Node = Node->Left;
    00294         }
    00295         else
    00296         if (Node->Parent)
    00297         {
    00298             while (Node && Node->Parent)
    00299             {
    00300                 if (Node->Parent->Left == Node)
    00301                 {
    00302                     Node = Node->Parent;
    00303                     break;
    00304                 }
    00305                 else
    00306                 {
    00307                     Node = Node->Parent;
    00308                     if (!Node->Parent)
    00309                         Node = NULL;
    00310                 }
    00311             }
    00312         }
    00313         else
    00314             Node = NULL;
    00315         if (Node)
    00316         {
    00317             obj = &(Node->Data);
    00318         }
    00319         return Node;
    00320     }
    00321     void* AddElement(const T & data)
    00322     {
    00323         TRBNode *Node, *NewNode = new TRBNode(data);
    00324         if (!NewNode)
    00325             return NULL;
    00326
    00327         NewNode->Tree = this;
    00328         m_Length++;
    00329         if (m_Root == NULL)
    00330             m_Root = NewNode;
    00331         else
    00332         {
    00333             Node = m_Root;
    00334             while (Node != NULL)
    00335             {
    00336                 if (*Node > data) // looks a little funky, but it's due to the operator order
    00337                 {
    00338                     if (Node->Left)
    00339                     {
    00340                         Node = Node->Left;
    00341                     }
    00342                     else
    00343                     {
    00344                         Node->Left = NewNode;
    00345                         NewNode->Parent = Node;
    00346                         break;
    00347                     }
    00348                 }
    00349                 else
    00350                 {
    00351                     if (Node->Right)
    00352                     {
    00353                         Node = Node->Right;
    00354                     }
    00355                     else
    00356                     {
    00357                         Node->Right = NewNode;
    00358                         NewNode->Parent = Node;
    00359                         break;
    00360                     }
    00361                 }
    00362             }
    00363         }
    00364
    00365         RestoreRedBlack(NewNode);
    00366
    00367         return NewNode;
    00368     }
    00369     static void StaticRemoveElement(void * ptr)
    00370     {
    00371         TRBNode * Node = (TRBNode*)ptr;
    00372         if (Node->Tree)
    00373             Node->Tree->RemoveElement(ptr);
    00374     }
    00375 #pragma todo (make sure RemoveElement really works)
    00376     deBoolean RemoveElement(void * ptr)
    00377     {
    00378         TRBNode * Node = (TRBNode*)ptr;
    00379         if (Node == NULL)
    00380             return deFALSE;
    00381         TRBNode * DeletedNode = NULL;
    00382         deBoolean LeftSide;
    00383
    00384         if (Node->Left && Node->Right)
    00385         {
    00386             // have two children. This is the "Nasty Case"
    00387             // but we can do a fancy trick by swapping that guarantees we have one or no children
    00388             // we swap with one that only has one child, and "delete" that one instead
    00389             TRBNode * Swapper = Node->Right;
    00390             // get the smallest value that's greater than value in 'Node'
    00391             while (Swapper->Left)
    00392             {
    00393                 Swapper = Swapper->Left;
    00394             }
    00395             Swapper->SwapWith(Node, m_Root);
    00396         }
    00397
    00398         if (Node->Left || Node->Right)
    00399         {
    00400             // we have a single child
    00401             if (Node->Right == NULL)
    00402             {
    00403                 // only have a left node
    00404                 DeletedNode = Node;
    00405                 Node->Left->Parent = Node->Parent;
    00406                 if (Node->Parent)
    00407                 {
    00408                     LeftSide = (Node->Parent->Left == Node);
    00409                     if (LeftSide)
    00410                     {
    00411                         Node->Parent->Left = Node->Left;
    00412                     }
    00413                     else //if (Node->Parent->Right == Node)
    00414                     {
    00415                         Node->Parent->Right = Node->Left;
    00416                     }
    00417                 }
    00418                 else
    00419                     m_Root = Node->Left;
    00420             }
    00421             else //if (Node->Left == NULL)
    00422             {
    00423                 // only have a right node
    00424                 DeletedNode = Node;
    00425                 Node->Right->Parent = Node->Parent;
    00426                 if (Node->Parent)
    00427                 {
    00428                     LeftSide = (Node->Parent->Left == Node);
    00429                     if (LeftSide)
    00430                     {
    00431                         Node->Parent->Left = Node->Right;
    00432                     }
    00433                     else //if (Node->Parent->Right == Node)
    00434                     {
    00435                         Node->Parent->Right = Node->Right;
    00436                     }
    00437                 }
    00438                 else
    00439                     m_Root = Node->Right;
    00440             }
    00441         }
    00442         else
    00443         {
    00444             //no children, just point the parent at NULL
    00445             DeletedNode = Node;
    00446             if (Node->Parent)
    00447             {
    00448                 LeftSide = (Node->Parent->Left == Node);
    00449                 if (LeftSide)
    00450                 {
    00451                     Node->Parent->Left = NULL;
    00452                 }
    00453                 else //if (Node->Parent->Right == Node)
    00454                 {
    00455                     Node->Parent->Right = NULL;
    00456                 }
    00457             }
    00458             else
    00459                 m_Root = NULL;
    00460         }
    00461
    00462         // deleting black affects the black-depth of the tree
    00463         // so we need to adjust & possibly rebalance
    00464         if (DeletedNode->Color == TRBNode::Black)
    00465         {
    00466             if (DeletedNode->Parent)
    00467             {
    00468                 // if it had a child, then the child was merely moved into its place and can be re-colored to black
    00469                 if (LeftSide && DeletedNode->Parent->Left)
    00470                 {
    00471                     DeletedNode->Parent->Left->Color = TRBNode::Black;
    00472                     goto GoodRet;
    00473                 }
    00474                 else if (!LeftSide && DeletedNode->Parent->Right)
    00475                 {
    00476                     DeletedNode->Parent->Right->Color = TRBNode::Black;
    00477                     goto GoodRet;
    00478                 }
    00479             }
    00480
    00481             {
    00482                 // deleted node was black leaf, this is the tough one
    00483                 TRBNode RootSentinel;
    00484                 TRBNode* Sibling;
    00485                 TRBNode* Current;
    00486                 TRBNode* NodeParent;
    00487                 m_Root->Parent = &RootSentinel;
    00488                 RootSentinel.Left = m_Root;
    00489                 RootSentinel.Right = NULL;
    00490                 Current = DeletedNode;
    00491                 NodeParent = Current->Parent;
    00492                 if (NodeParent)
    00493                     Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
    00494                 else
    00495                     Sibling = NULL;
    00496                 // Loop until the current node is red, or until we get to the root node.
    00497                 while (NodeParent->Parent && Current->Color == TRBNode::Black)
    00498                 {
    00499                     // If the sibling is red, we are unable to reduce the number of black
    00500                     // nodes in the sibling tree, and we can't increase the number of
    00501                     // black nodes in our tree..  Thus we must do a rotation from the
    00502                     // sibling tree to our tree to give us some extra (red) nodes to
    00503                     // play with. This is Case 1 from the text
    00504                     if (Sibling && Sibling->Color == TRBNode::Red)
    00505                     {
    00506                         NodeParent->Color = TRBNode::Red;
    00507                         Sibling->Color = TRBNode::Black;
    00508                         if (LeftSide)
    00509                         {
    00510                             leftRotate(NodeParent);
    00511                             Sibling = NodeParent->Right;
    00512                         }
    00513                         else
    00514                         {
    00515                             rightRotate(NodeParent);
    00516                             Sibling = NodeParent->Left;
    00517                         }
    00518                         continue;
    00519                     }
    00520                     // Sibling will be black here
    00521
    00522                     // If the sibling is black and has no red children, we have to
    00523                     // reduce the black node count in the sibling's tree to match ours.
    00524                     // This is Case 2a from the text.
    00525                     if (!Sibling ||
    00526                         ((!Sibling->Left || Sibling->Left->Color == TRBNode::Black) &&
    00527                          (!Sibling->Right|| Sibling->Right->Color== TRBNode::Black)))
    00528                     {
    00529                         if (Sibling)
    00530                             Sibling->Color = TRBNode::Red;
    00531                         // Now we move one level up the tree to continue fixing the other branches.
    00532                         Current = NodeParent;
    00533                         NodeParent = Current->Parent;
    00534                         LeftSide = (NodeParent->Left == Current);
    00535                         Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
    00536                         continue;
    00537                     }
    00538                     // Sibling will be black with 1 or 2 red children here
    00539
    00540                     // << Case 2b is handled by the while loop. >>
    00541
    00542                     // If one of the sibling's children are red, we again can't make the
    00543                     // sibling red to balance the tree at the parent, so we have to do a
    00544                     // rotation.  If the "near" nephew is red and the "far" nephew is
    00545                     // black, we need to do a "prep-slide" (aka "double rotation")
    00546                     // After doing a rotation and rearranging a few colors, the effect is
    00547                     // that we maintain the same number of black nodes per path on the
    00548                     // far side of the parent, and we gain a black node on the current
    00549                     // side, so we are done.
    00550                     // This is Case 4 from the text. (Case 3 is the double rotation)
    00551                     if (LeftSide)
    00552                     {
    00553                         if (Sibling->Right->Color == TRBNode::Black)
    00554                         { // Case 3 from text
    00555                             rightSide_RightRotate(Sibling);
    00556                             Sibling = NodeParent->Right;
    00557                         }
    00558                         // now Case 4 from the text
    00559                         if (Sibling->Right->Color != TRBNode::Black ||
    00560                             Sibling->Color != NodeParent->Color ||
    00561                             NodeParent->Color != TRBNode::Black)
    00562                         {
    00563                             Sibling->Right->Color = TRBNode::Black;
    00564                             Sibling->Color = NodeParent->Color;
    00565                             NodeParent->Color = TRBNode::Black;
    00566                         }
    00567
    00568                         Current = NodeParent;
    00569                         NodeParent = Current->Parent;
    00570                         // I would have assigned to leftSide here,
    00571                         //   but we are exiting the function, so why bother?
    00572                         // leftSide= (Parent->Left == Current);
    00573                         if (NodeParent->Left == Current)
    00574                             leftSide_LeftRotate(Current);
    00575                         else
    00576                             rightSide_LeftRotate(Current);
    00577                         goto GoodRet;
    00578                     }
    00579                     else
    00580                     {
    00581                         if (Sibling->Left->Color == TRBNode::Black)
    00582                         { // Case 3 from text
    00583                             leftSide_LeftRotate(Sibling);
    00584                             Sibling = NodeParent->Left;
    00585                         }
    00586                         // Case 4 from the text
    00587                         if (Sibling->Left->Color != TRBNode::Black ||
    00588                             Sibling->Color != NodeParent->Color ||
    00589                             NodeParent->Color != TRBNode::Black)
    00590                         {
    00591                             Sibling->Left->Color = TRBNode::Black;
    00592                             Sibling->Color = NodeParent->Color;
    00593                             NodeParent->Color = TRBNode::Black;
    00594                         }
    00595
    00596                         Current = NodeParent;
    00597                         NodeParent = Current->Parent;
    00598                         // I would have assigned to leftSide here,
    00599                         // but we are exiting the function, so why bother?
    00600                         // leftSide = (Parent->Left == Current);
    00601                         if (NodeParent->Left == Current)
    00602                             leftSide_LeftRotate(Current);
    00603                         else
    00604                             rightSide_LeftRotate(Current);
    00605                         goto GoodRet;
    00606                     }
    00607                     // Now, make the current node black (to fulfill Case 2b)
    00608                     // Case 4 will have exited directly out of the function.
    00609                     // If we stopped because we reached the top of the tree,
    00610                     //   the head is black anyway so don't worry about it.
    00611                     Current->Color = TRBNode::Black;
    00612                 }
    00613                 m_Root = RootSentinel.Left;
    00614                 if (m_Root)
    00615                     m_Root->Parent = NULL;
    00616             }
    00617         }
    00618 GoodRet:
    00619         if (m_Root)
    00620             DE_ASSERT(m_Root->Color == TRBNode::Black);
    00621         delete Node;
    00622         m_Length--;
    00623         return deTRUE;
    00624     }
    00625     T* GetData(void* ptr)
    00626     {
    00627         TRBNode * Node = (TRBNode*)ptr;
    00628         if (Node == NULL)
    00629             return NULL;
    00630         return &(Node->Data);
    00631     }
    00632     void GetDataPList(deTList <T*> &list)
    00633     {
    00634         if (m_Root)
    00635             m_Root->AddDataToList(list);
    00636     }
    00637     long Length() const
    00638     {
    00639         return m_Length;
    00640     }
    00641 private:
    00642     void RestoreRedBlack(TRBNode * Node)
    00643     {
    00644         if (!Node)
    00645             return;
    00646         TRBNode* Uncle;
    00647         /* Now restore the red-black property */
    00648         Node->Color = TRBNode::Red;
    00649         while ( (Node != m_Root) && (Node->Parent->Color == TRBNode::Red) )
    00650         {
    00651             if ( Node->Parent == Node->Parent->Parent->Left )
    00652             {
    00653                 /* If x's parent is a left, y is x's right 'uncle' */
    00654                 Uncle = Node->Parent->Parent->Right;
    00655                 if (Uncle && Uncle->Color == TRBNode::Red )
    00656                 {
    00657                     /* case 1 - change the colours */
    00658                     Node->Parent->Color = TRBNode::Black;
    00659                     Uncle->Color = TRBNode::Black;
    00660                     Node->Parent->Parent->Color = TRBNode::Red;
    00661                     /* Move x up the tree */
    00662                     Node = Node->Parent->Parent;
    00663                 }
    00664                 else
    00665                 {
    00666                     /* y is a black node */
    00667                     if ( Node == Node->Parent->Right )
    00668                     {
    00669                         /* and x is to the right */
    00670                         /* case 2 - move x up and rotate */
    00671                         Node = Node->Parent;
    00672                         RotateLeft( Node );
    00673                     }
    00674                     /* case 3 */
    00675                     Node->Parent->Color = TRBNode::Black;
    00676                     Node->Parent->Parent->Color = TRBNode::Red;
    00677                     RotateRight( Node->Parent->Parent );
    00678                 }
    00679             }
    00680             else
    00681             {
    00682                 /* If x's parent is a right, y is x's left 'uncle' */
    00683                 Uncle = Node->Parent->Parent->Left;
    00684                 if (Uncle && Uncle->Color == TRBNode::Red )
    00685                 {
    00686                     /* case 1 - change the colours */
    00687                     Node->Parent->Color = TRBNode::Black;
    00688                     Uncle->Color = TRBNode::Black;
    00689                     Node->Parent->Parent->Color = TRBNode::Red;
    00690                     /* Move x up the tree */
    00691                     Node = Node->Parent->Parent;
    00692                 }
    00693                 else
    00694                 {
    00695                     /* y is a black node */
    00696                     if ( Node == Node->Parent->Left )
    00697                     {
    00698                         /* and x is to the right */
    00699                         /* case 2 - move x up and rotate */
    00700                         Node = Node->Parent;
    00701                         RotateRight( Node );
    00702                     }
    00703                     /* case 3 */
    00704                     Node->Parent->Color = TRBNode::Black;
    00705                     Node->Parent->Parent->Color = TRBNode::Red;
    00706                     RotateLeft( Node->Parent->Parent );
    00707                 }
    00708             }
    00709         }
    00710         /* Colour the root black */
    00711         m_Root->Color = TRBNode::Black;
    00712     }
    00713     void RotateLeft(TRBNode * Node)
    00714     {
    00715         TRBNode * y;
    00716         y = Node->Right;
    00717         /* Turn y's left sub-tree into x's right sub-tree */
    00718         Node->Right = y->Left;
    00719         if ( y->Left != NULL )
    00720             y->Left->Parent = Node;
    00721         /* y's new parent was x's parent */
    00722         y->Parent = Node->Parent;
    00723         /* Set the parent to point to y instead of x */
    00724         /* First see whether we're at the root */
    00725         if ( Node->Parent == NULL )
    00726             m_Root = y;
    00727         else
    00728         {
    00729             if ( Node == (Node->Parent)->Left )
    00730                 /* x was on the left of its parent */
    00731                 Node->Parent->Left = y;
    00732             else
    00733                 /* x must have been on the right */
    00734                 Node->Parent->Right = y;
    00735         }
    00736         /* Finally, put x on y's left */
    00737         y->Left = Node;
    00738         Node->Parent = y;
    00739     }
    00740     void RotateRight(TRBNode * Node)
    00741     {
    00742         TRBNode * y;
    00743         y = Node->Left;
    00744         /* Turn y's right sub-tree into x's left sub-tree */
    00745         Node->Left = y->Right;
    00746         if ( y->Right != NULL )
    00747             y->Right->Parent = Node;
    00748         /* y's new parent was x's parent */
    00749         y->Parent = Node->Parent;
    00750         /* Set the parent to point to y instead of x */
    00751         /* First see whether we're at the root */
    00752         if ( Node->Parent == NULL )
    00753             m_Root = y;
    00754         else
    00755         {
    00756             if ( Node == (Node->Parent)->Right )
    00757                 /* x was on the right of its parent */
    00758                 Node->Parent->Right = y;
    00759             else
    00760                 /* x must have been on the left */
    00761                 Node->Parent->Left = y;
    00762         }
    00763         /* Finally, put x on y's right */
    00764         y->Right = Node;
    00765         Node->Parent = y;
    00766     }
    00767
    00768     void rightRotate(TRBNode* node)
    00769     {
    00770         if (node->Parent->Left == node)
    00771             leftSide_RightRotate(node);
    00772         else
    00773             rightSide_RightRotate(node);
    00774     }
    00775
    00776     void leftRotate(TRBNode* node)
    00777     {
    00778         if (node->Parent->Left == node)
    00779             leftSide_LeftRotate(node);
    00780         else
    00781             rightSide_LeftRotate(node);
    00782     }
    00783
    00784     void leftSide_LeftRotate(TRBNode* node)
    00785     {
    00786         TRBNode* temp = node->Parent; // temp is used for parent
    00787         TRBNode* child = node->Right;
    00788
    00789         temp->Left = child;
    00790         child->Parent = temp;
    00791
    00792         temp = child->Left; // temp is now used for grandchild
    00793         node->Right = temp;
    00794         temp->Parent = node;
    00795
    00796         child->Left = node;
    00797         node->Parent = child;
    00798     }
    00799
    00800     void leftSide_RightRotate(TRBNode* node)
    00801     {
    00802         TRBNode* temp = node->Parent; // temp is used for parent
    00803         TRBNode* child = node->Left;
    00804
    00805         temp->Left = child;
    00806         child->Parent = temp;
    00807
    00808         temp = child->Right; // temp is now used for grandchild
    00809         node->Left = temp;
    00810         temp->Parent = node;
    00811
    00812         child->Right = node;
    00813         node->Parent = child;
    00814     }
    00815
    00816     void rightSide_RightRotate(TRBNode* node)
    00817     {
    00818         TRBNode* temp = node->Parent; // temp is used for parent
    00819         TRBNode* child = node->Left;
    00820
    00821         temp->Right = child;
    00822         child->Parent = temp;
    00823
    00824         temp = child->Right; // temp is now used for grandchild
    00825         node->Left = temp;
    00826         temp->Parent = node;
    00827
    00828         child->Right = node;
    00829         node->Parent = child;
    00830     }
    00831
    00832     void rightSide_LeftRotate(TRBNode* node)
    00833     {
    00834         TRBNode* temp = node->Parent; // temp is used for parent
    00835         TRBNode* child = node->Right;
    00836
    00837         temp->Right = child;
    00838         child->Parent = temp;
    00839
    00840         temp = child->Left; // temp is now used for grandchild
    00841         node->Right = temp;
    00842         temp->Parent = node;
    00843
    00844         child->Left = node;
    00845         node->Parent = child;
    00846     }
    00847
    00848 };
    00849
    00850 //#pragma warning (default : 4710)
    00851
    00852 #endif // DEREDBLACK_HPP