登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Gamebaby Rock Sun的博客

我只知道一件事情,就是我一无所知。

 
 
 

日志

 
 
关于我

曾经拥有的,不要忘记, 已经得到的,更要珍惜, 属于自己的,不要放弃, 已经失去的,留着回忆, 想要得到的,必须努力, 但最重要的,是好好爱惜自己!

我实现的红黑树C++模版类  

2008-04-06 21:56:10|  分类: VC/VC++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       下面是我实现的红黑树C++模版类,利用了windows中的一些特性,关于红黑树的算法我不再赘述,大家自己搜索一下,满网络都是,此处的实现是一个非常好用的模版版本。可以免费用于任何用途,在版本升级或发生变动后,本人将不通知任何使用者,但是如果需要技术支持、升级服务或培训服务的可以与本人联系,QQ 41750362。

//红黑树
#include "GRSPublicDef.h"
#include "GRSNew.h"
#pragma once

enum EM_GRS_RBCOLOR
{
 GRS_RED = 0x0L,
 GRS_BLACK
};

template <class TKey,class TData>
class CGRSRBNode
{
protected:
 TKey m_Key;
 TData m_Data;

 EM_GRS_RBCOLOR m_Color;

 CGRSRBNode<TKey,TData>* m_pParent;
 CGRSRBNode<TKey,TData>* m_pLeft;
 CGRSRBNode<TKey,TData>* m_pRight;
public:
 friend class CGRSRBTree;
public:
 CGRSRBNode(TKey Key,TData Data,
  EM_GRS_RBCOLOR m_Color = GRS_BLACK,
  CGRSRBNode<TKey,TData>* pParent = NULL,
  CGRSRBNode<TKey,TData>* pLeft = NULL,
  CGRSRBNode<TKey,TData>* pRight = NULL)
  :m_Key(Key),
  m_Data(Data),
  m_Color(m_Color),
  m_pParent(pParent),
  m_pLeft(pLeft),
  m_pRight(pRight)
 {
 }

 virtual ~CGRSRBNode()
 {
 }
};

template <class TKey,class TData>
class CGRSRBTree
{
protected:
 CGRSRBNode<TKey,TData>* m_pRoot;
public:
 CGRSRBTree()
  :m_pRoot(NULL)
 {
 }
 virtual ~CGRSRBTree()
 {
 }
protected:
 void DelTree( CGRSRBNode<TKey,TData>*& pNode)
 {
  if(NULL != pNode)
  {
   CGRSRBNode<TKey,TData>* pTmp = pNode->m_pRight;
   Core_DelTree( pNode->m_pLeft);
   delete pNode;
   pNode = NULL;
   Core_DelTree(pTmp);
  }
 }
 //______________________________________________________________//
 //                                                              //
 //     |                                 |                      //
 //     A       LeftRotation()            B                      //
 //    / \     ---------------->         / \                     //
 //   1   B    <----------------        A   3                    //
 //      / \    RightRotation()        / \                       //
 //     2   3                         1   2                      //
 //______________________________________________________________//
 void LeftRotation( CGRSRBNode<TKey,TData>* pRotation )
 { 
  CGRSRBNode<TKey,TData>* pTmp  = pRotation->m_pRight;

  if( NULL == pTmp )
  {
   return;
  }

  pRotation->m_pRight = pTmp->m_pLeft;

  if( NULL != pTmp->m_pLeft )
  {
   pTmp->m_pLeft->m_pParent = pRotation;
  }

  pTmp->m_pParent = pRotation->m_pParent;

  if( NULL == pRotation->m_pParent )
  {
   m_pRoot = pTmp;
  }
  else if( pRotation == pRotation->m_pParent->m_pLeft )
  {
   pRotation->m_pParent->m_pLeft = pTmp;
  }
  else
  {
   pRotation->m_pParent->m_pRight =pTmp;
  }

  pTmp->m_pLeft = pRotation;
  pRotation->m_pParent = pTmp;
 }

 void RightRotation(CGRSRBNode<TKey,TData>* pRotation)
 {
  CGRSRBNode<TKey,TData>* pTmp = pRotation->m_pLeft;
  if(NULL == pTmp)
  {
   return;
  }

  pRotation->m_pLeft = pTmp->m_pRight;

  if( NULL != pTmp->m_pRight )
  {
   pTmp->m_pRight->m_pParent = pRotation;
  }

  pTmp->m_pParent = pRotation->m_pParent;

  if( NULL == pRotation->m_pParent )
  {
   m_pRoot = pTmp;
  }
  else if (pRotation== pRotation->m_pParent->m_pRight)
  {
   pRotation->m_pParent->m_pRight = pTmp;
  }
  else
  {
   pRotation->m_pParent->m_pLeft = pTmp;
  }

  pTmp->m_pRight  = pRotation;
  pRotation->m_pParent = pTmp;
 }

 void AddFixup(CGRSRBNode<TKey,TData>* pFix)
 {   
  CGRSRBNode<TKey,TData>* pTmp = NULL;

  while( m_pRoot != pFix
   && GRS_RED == pFix->m_pParent->m_Color )
  {
   if( pFix->m_pParent == pFix->m_pParent->m_pParent->m_pLeft )
   {
    pTmp =  pFix->m_pParent->m_pParent->m_pRight;

    if(pTmp != NULL && GRS_RED == pTmp->m_Color )
    {//只修改颜色
     pFix->m_pParent->m_Color = GRS_BLACK;
     pTmp->m_Color = GRS_BLACK;
     pFix->m_pParent->m_pParent->m_Color = GRS_RED;
     pFix = pFix->m_pParent->m_pParent;
    }
    else
    {//旋转
     if( pFix == pFix->m_pParent->m_pRight)
     {
      pFix = pFix->m_pParent;
      LeftRotation(pFix);
     }

     pFix->m_pParent->m_Color = GRS_BLACK;
     pFix->m_pParent->m_pParent->m_Color = GRS_RED;

     RightRotation(pFix->m_pParent->m_pParent);
    }

   }

   else
   {    
    pTmp =  pFix->m_pParent->m_pParent->m_pLeft;

    if(pTmp != NULL && pTmp->m_Color == GRS_RED  )
    {//只修改颜色
     pFix->m_pParent->m_Color = GRS_BLACK;
     pTmp->m_Color = GRS_BLACK;
     pFix->m_pParent->m_pParent->m_Color = GRS_RED;
     pFix = pFix->m_pParent->m_pParent;
    }
    else
    {//旋转
     if (pFix == pFix->m_pParent->m_pLeft)
     {
      pFix = pFix->m_pParent;
      RightRotation(pFix);
     }

     pFix->m_pParent->m_Color = GRS_BLACK;
     pFix->m_pParent->m_pParent->m_Color = GRS_RED;
     LeftRotation(pFix->m_pParent->m_pParent);
    }

   }
  }
  m_pRoot->m_Color = GRS_BLACK;
 }

 void DelFixUp(CGRSRBNode<TKey,TData>* pFix)
 {  
  CGRSRBNode<TKey,TData>* pTmp = NULL;
  CGRSRBNode<TKey,TData>* pFixTmp = NULL;
  
  while( pFix != m_pRoot && GRS_BLACK == pFix->m_Color )
  {
   if( pFix == pFix->m_pParent->m_pLeft )
   {
    pFixTmp = pFix->m_pParent->m_pRight;
    
    if( NULL == pFixTmp )
    {
     continue;
    }

    if(pFixTmp->m_Color == GRS_RED)
    {
     pFixTmp->m_Color = GRS_BLACK;
     pFix->m_pParent->m_Color = GRS_RED;
     LeftRotation(pFix->m_pParent);
     pFixTmp = pFix->m_pParent->m_pRight;
    }

    if( NULL != pFixTmp->m_pLeft && GRS_BLACK == pFixTmp->m_pLeft->m_Color &&
     NULL != pFixTmp->m_pRight && GRS_BLACK == pFixTmp->m_pRight->m_Color)
    {
     pFixTmp->m_Color = GRS_RED;
     pFix = pFix->m_pParent;
    }
    else
    {
     if(NULL != pFixTmp->m_pRight && GRS_BLACK == pFixTmp->m_pRight->m_Color)
     {
      pFixTmp->m_pLeft->m_Color = GRS_BLACK;
      pFixTmp->m_Color = GRS_RED;
      RightRotation(pFixTmp);
      pFixTmp = pFix->m_pParent->m_pRight;
     }

     pFixTmp->m_Color = pFix->m_pParent->m_Color;
     pFix->m_pParent->m_Color = GRS_BLACK;
     pFixTmp->m_pRight->m_Color = GRS_BLACK;
     LeftRotation(pFix->m_pParent);
     pFix = m_pRoot;
    }
   }
   else
   {
    pFixTmp = pFix->m_pParent->m_pLeft;
    if(NULL == pFixTmp)
    {
     continue;
    }

    if(GRS_RED == pFixTmp->m_Color)
    {  
     pFixTmp->m_Color = GRS_BLACK;
     pFix->m_pParent->m_Color = GRS_RED;
     RightRotation(pFix->m_pParent);
     pTmp = pFix->m_pParent->m_pLeft;
    }

    if(NULL != pFixTmp->m_pLeft && GRS_BLACK == pFixTmp->m_pLeft->m_Color &&
     NULL != pFixTmp->m_pRight && GRS_BLACK == pFixTmp->m_pRight->m_Color)
    { 
     pFixTmp->m_Color = GRS_RED;
     pFix = pFix->m_pParent;
    }
    else
    {
     if(NULL != pFixTmp->m_pLeft && pFixTmp->m_pLeft->m_Color == GRS_BLACK)
     {
      pFixTmp->m_pRight->m_Color = GRS_BLACK;
      pFixTmp->m_Color = GRS_RED;
      LeftRotation(pFixTmp);
      pFixTmp = pFix->m_pParent->m_pLeft;
     }

     pFixTmp->m_Color = pFixTmp->m_pParent->m_Color;
     pFixTmp->m_pParent->m_Color = GRS_BLACK;
     pFixTmp->m_pLeft->m_Color = GRS_BLACK;
     RightRotation(pFixTmp->m_pParent);
     pFix = m_pRoot;
    }

   }
  }
  pFix->m_Color = GRS_BLACK;
 }

 CGRSRBNode<TKey,TData>* GetMinNode(CGRSRBNode<TKey,TData>* pNode)
 {
  while( NULL != pNode->m_pLeft )
  {
   pNode = pNode->m_pLeft;
  }
  return pNode;
 }

 CGRSRBNode<TKey,TData>* NodeHealth(CGRSRBNode<TKey,TData>* pNode)
 {
  if ( NULL != pNode->m_pRight )
  {
   return GetMinNode( pNode->m_pRight );
  }

  CGRSRBNode<TKey,TData>* pTmp = pNode->m_pParent;
 
  while( ( pTmp != NULL ) && ( pNode == pNode->m_pRight ) )
  {
   pNode = pTmp;
   pTmp = pTmp->m_pParent;
  }

  return pTmp;
 }
public:
 GRSPOSITION Search( const TKey& Key, TData& Data )
 {
  CGRSRBNode<TKey,TData>* pRet = NULL;
  CGRSRBNode<TKey,TData>* pTmpNode = m_pRoot;
  while( NULL != pTmpNode )
  {
   if( Key < pTmpNode->m_Key )
   {
    pTmpNode = pTmpNode->m_pLeft;
   }
   else if( Key > pTmpNode->m_Key )
   {
    pTmpNode = pTmpNode->m_pRight;
   }
   else
   {
    pRet = pTmpNode;
    Data = pRet->m_Data;
    break;
   }
  }
  return (GRSPOSITION) pRet;
 }

 BOOL Add(const TKey& Key,const TData& Data)
 {
  TData tmpData;
  if( Search(Key,tmpData) )
  {//不允许插入重复值
   return FALSE;
  }

  CGRSRBNode<TKey,TData>* pRoot = m_pRoot;
  CGRSRBNode<TKey,TData>* pNew = new CGRSRBNode<TKey,TData>(Key,Data,GRS_RED); //将要插入的结点
  CGRSRBNode<TKey,TData>* pTmp = NULL;
  
  pTmp = pRoot;
  while( pTmp != NULL )
  {
   if( pNew->m_Key < pTmp->m_Key )
   {
    if( NULL != pTmp->m_pLeft )
    {
     pTmp = pTmp->m_pLeft;
    }
    else
    {
     break;
    }
   }
   else
   {   
    if( NULL != pTmp->m_pRight )
    {
     pTmp = pTmp->m_pRight;
    }
    else
    {
     break;
    }
   }
  }

  pNew->m_pParent = pTmp;

  if( pTmp == NULL )
  {
   m_pRoot = pNew;
  }
  else if( pNew->m_Key < pTmp->m_Key )
  {
   pTmp->m_pLeft = pNew;
  }
  else
  {
   pTmp->m_pRight = pNew;
  }

  AddFixup(pNew);

  return (NULL != pNew);
 }


 BOOL Del(const TKey& Key,TData& Data )
 {    
  CGRSRBNode<TKey,TData>* pNode1 = NULL;
  CGRSRBNode<TKey,TData>* pNode2 = NULL;
  
  CGRSRBNode<TKey,TData>* pDel = (CGRSRBNode<TKey,TData>*) Search( Key,Data );//找到此结点
  if( NULL == pDel )
  {
   return FALSE;
  }

  if( ( NULL == pDel->m_pLeft ) || ( NULL == pDel->m_pRight ) )
  {
   pNode2 = pDel;
  }
  else
  {
   pNode2 = NodeHealth( pDel );
  }

  if( NULL != pNode2->m_pLeft )
  {
   pNode1 = pNode2->m_pLeft;
  }
  else
  {
   pNode1 = pNode2->m_pRight;
  }

  pNode1->m_pParent = pNode2->m_pParent;

  if( NULL == pNode2->m_pParent )
  {
   m_pRoot = pNode1;
  }
  else if(pNode2 == pNode2->m_pParent->m_pLeft)
  {
   pNode2->m_pParent->m_pLeft = pNode1;
  }
  else
  {
   pNode2->m_pParent->m_pRight = pNode1;
  }

  if( pNode2 != pDel )
  {
   pDel->m_Key = pNode2->m_Key;
  }

  if( pNode2->m_Color == GRS_BLACK && NULL != pNode1 )
  {
   RBDeleteFixUp(pNode1);
  }

  delete pNode2;

  return TRUE;
 }
 void Destroy(void)
 {
  if( m_pRoot )
  {
   Core_DelTree( m_pRoot );
   m_iCount = 0;
  }
 }
};

 

注意这个版本中我撒了懒,没有写遍历的接口,需要的可以参考本人的AVL树中的版本自行复制添加即可。

  评论这张
 
阅读(1620)| 评论(1)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018