织梦CMS - 轻松建站从此开始！
高级搜索|网站地图|TAG标签RSS订阅[设为首页] [加入收藏]

罗索

搜索

热门标签:

当前位置: 主页>基础技术>C/CPP专题>

红黑树的C++实现

落鹤生 发布于 2012-07-13 09:40 点击:次 
在实现之前网上浏览了一下,看到很多人都有自己的实现.主要的实现方式都是受了Introduction to Algorithm的影响.代码的结构和书中给出的伪码如出一辙,但是问题大都是1,没有深刻的理解FixUp和到底哪个节点需要. 2,忽略了Sentinel也就是哨兵节点的存在的意义.C/C++实现中的
TAG:

在实现之前网上浏览了一下,看到很多人都有自己的实现.主要的实现方式都是受了Introduction to Algorithm的影响.代码的结构和书中给出的伪码如出一辙,但是问题大都是1,没有深刻的理解FixUp和到底哪个节点需要. 2,忽略了Sentinel也就是哨兵节点的存在的意义.C/C++实现中的NULL在指代上还是出现了一点偏差.

这里我们比较关心插入和删除操作(查询和普通的BST没有差别,不赘述了)
现在我们来具体分析一下插入操作
1. 首先父亲节点如果是黑色节点的话,不需要处理了,多一个红色节点不会有任何影响.
2. 如果父亲节点是红色的,而叔父节点也是红色,那就是把父亲和叔父节点同时改成黑色,然后递归的向上传递.
3. 如果父亲节点是红色的,而叔父节点是黑色的. 后面的话比较拗口.父亲是祖父的左孩子.
   (1)如果自己是父亲的左孩子,那么修改父亲和祖父的颜色然后右转祖父
   (2)如果自己是父亲的有孩子,那么先做左转父亲,在把自己指向父亲,执行(1).
类似的描述很多地方都有,这个过程也是比较清晰,所以不存在什么错误.而且比较清楚的问题就是需要FixUp的就是当前新加入的节点.

问题呢集中体现在删除的地方.这个是网上看到的一个实现,这里一样,也遵循了算法导论中的命名方式:p,x,y分别有了自己的定义:
    RBTreeNode *p = NULL; //指向查找到的节点(实际上可能并不删除它)
    RBTreeNode *x = NULL; //指向欲删除的节点(可能和p一样)
    RBTreeNode *y = NULL; //指向欲删除节点的子节点(欲删除节点只有一个子节点)
但是在很多情况下y都是NULL,(当然实际意义上是哨兵节点啦). 所以看到很多代码选择了FixUp X节点的父亲节点.但实际上
这个意义其实是完全不一样的 我们来看一个我碰到的具体的例子就很明白了,一棵树在插入了1-20以后呈现出这样的形态

比 如我现在要删除10这个节点,那么显然p就是10这个节点,而x是什么的,x就是max(p->left)或者min(p->right). 现在这个例子中就是9或者11,我们假定选择9.而y是什么呢就是9的子节点(也即是我们说的哨兵节点).那这个时候需要FixUp的节点是什么呢??

由网上的一些实现看来是
            if (y != NULL)
            {
                DeleteFixup(y);
            }
            else
            {
                DeleteFixup(x->parent);
            }
X 的父亲,也就是10这个节点,这样的话,兄弟节点的右子节点为红色,直接进入了Delete Case4做改色(12改成黑色,16红色18黑色),然后左旋转12.这个时候我们发现,转了以后并不平衡,显然违反了红黑树的定义,在12-9-11 这个分支上有连续3个黑色节点,显然多余了其他的12-14-13和12-14-15. 而造成这一切的元凶就是FixUp的错误的开始.

   其实一样,我们还是应该按照定义来,还是从y开始更新,但是y表面上看起来是NULL,怎么FixUp呢?这个时候哨兵节点的作用得以体现,我们把每个叶 子节点的left/right都指向一个哨兵节点,哨兵节点的颜色是黑色,而且left/right就是NULL,这样我们就可以用这个哨兵节点来做 FixUp了.同时省去了在Fixup中冗余的NULL的判断,这里的指针就一直是有效的了.所以在这个case中我们实际上下一个w就是右边的黑色哨兵 节点,所以x和w都是黑色,所以进入了deleteFixUp的case2,只有把11改成了红色之后才继续向上递归的FixUp.这个实现其实给我很多 的感触.人的烦恼有很多,但无非是生活是复杂的,你把他想简单了,或者生活是简单的,你把他想复杂了:)

最后要说一点,在插入和删除操作有会有可能导致红黑树出现不平衡的情况,这个时候需要FixUp,但是最合理的实现是在操作结束后加入一段debug assert的代码用以检查平衡度的正确性,至少可以避免明显错误的尴尬:)
最后给出了所有的代码:

  1. #pragma once 
  2. #ifdef MY_DEBUG 
  3. #include <queue> 
  4. #include "assert.h" 
  5. #endif //MY_DEBUG 
  6. namespace ScanbuyLib{ 
  7.     enum rg_color  { black, red } ; 
  8.     enum e_balance { left_higher, equal_height, right_higher }; 
  9.     enum e_return  { e_success, e_fail, e_empty, e_duplicate, e_not_found }; 
  10.     enum e_order   { e_preorder, e_inorder, e_postorder }; 
  11.     template <class K, class V> class RBTreeNode  
  12.     { 
  13.     public: 
  14.         RBTreeNode(rg_color color = black); 
  15.         RBTreeNode(const K& key, const V& value, rg_color color= black); 
  16.     public: 
  17.         RBTreeNode<K,V>* m_pRChild; 
  18.         RBTreeNode<K,V>* m_pLChild; 
  19.         RBTreeNode<K,V>* m_pParent; 
  20.         K key; 
  21.         V value; 
  22.         rg_color color; 
  23.     }; 
  24.     template<class K, class V> RBTreeNode<K, V>::RBTreeNode(rg_color color) 
  25.     { 
  26.         m_pRChild = NULL; 
  27.         m_pLChild = NULL; 
  28.         m_pParent = NULL; 
  29. //      key = K(0); 
  30. //      value = V(0); 
  31.         this->color = color; 
  32.     } 
  33.     template<class K, class V>RBTreeNode<K, V>::RBTreeNode(const K& key
  34. , const V& value, rg_color color) 
  35.     { 
  36.         m_pRChild = NULL; 
  37.         m_pLChild = NULL; 
  38.         m_pParent = NULL; 
  39.         this->key = key; 
  40.         this->value = value; 
  41.         this->color = color; 
  42.     } 
  43.     template <class K, class V> class RedBlackTree 
  44.     { 
  45.     public: 
  46.         RedBlackTree(); 
  47.         ~RedBlackTree(); 
  48.         e_return insert(const K& key, const V& value); 
  49.         e_return remove(const K& key); 
  50.         e_return search(const K& key, V& value); // value as output 
  51.     private: 
  52.          
  53.         void destroy(RBTreeNode<K, V>* pNode); 
  54.         // make copy constructor and = operator private currently. 
  55.         RedBlackTree(const RedBlackTree&); 
  56.         RedBlackTree& operator = (const RedBlackTree& other); 
  57.          
  58.         RBTreeNode<K, V>* getGrandParent(RBTreeNode<K, V>* pNode); 
  59.         RBTreeNode<K, V>* getUncle(RBTreeNode<K, V>* pNode);     
  60.         RBTreeNode<K, V>* getSibling(RBTreeNode<K, V>* pNode); 
  61. #ifdef MY_DEBUG 
  62.         bool checkCorrectNess(); 
  63. #endif //MY_DEBUG 
  64.         void insertFixup(RBTreeNode<K, V>* pNode); 
  65.         void removeFixup(RBTreeNode<K, V>* pNode); 
  66.         void rotateLeft (RBTreeNode<K, V>* pNode); 
  67.         void rotateRight(RBTreeNode<K, V>* pNode); 
  68.         RBTreeNode<K, V>* m_pRoot; 
  69.         RBTreeNode<K, V>* m_pSentinel; 
  70.     }; 
  71.  
  72.     template <class K, class V>RedBlackTree<K, V>::RedBlackTree() 
  73.     { 
  74.         // first instantiate the sentinel node, then make it root as sentinel 
  75.         m_pSentinel = new RBTreeNode<K,V>(); 
  76.         m_pSentinel->m_pLChild = NULL; 
  77.         m_pSentinel->m_pRChild = NULL; 
  78.         m_pSentinel->m_pParent = NULL; 
  79.         m_pSentinel->color = black; 
  80.         m_pRoot = m_pSentinel; 
  81.     } 
  82.     template <class K, class V>RedBlackTree<K, V>::~RedBlackTree() 
  83.     { 
  84.         // TODO, need to add it once really use it!!!! 
  85.         destroy(m_pRoot); 
  86.         if (m_pSentinel) 
  87.         { 
  88.             delete m_pSentinel; 
  89.             m_pSentinel = NULL; 
  90.         } 
  91.     } 
  92.      
  93.     template <class K, class V>  void RedBlackTree<K, V>::destroy(RBTreeNode<K, V>* pNode) 
  94.     { 
  95.         if (pNode != NULL && pNode != m_pSentinel) 
  96.         { 
  97.             destroy(pNode->m_pLChild); 
  98.             destroy(pNode->m_pRChild);   
  99.             delete pNode; 
  100.             pNode = NULL; 
  101.         } 
  102.     } 
  103.     template <class K, class V>  RBTreeNode<K, V>* RedBlackTree<K
  104. , V>::getGrandParent(RBTreeNode<K, V>* pNode) 
  105.     { 
  106.         if (pNode && pNode->m_pParent) 
  107.             return pNode->m_pParent->m_pParent; 
  108.         else  
  109.             return NULL; 
  110.     } 
  111.     template <class K, class V> RBTreeNode<K, V>* RedBlackTree<K
  112. , V>::getUncle(RBTreeNode<K, V>* pNode) 
  113.     { 
  114.         RBTreeNode<K, V>* pTemp = getGrandParent(pNode); 
  115.         if (pTemp == NULL) 
  116.             return NULL; // No grandparent means no uncle 
  117.         if (pNode->m_pParent == pTemp->m_pLChild) 
  118.             return pTemp->m_pRChild; 
  119.         else 
  120.             return pTemp->m_pLChild; 
  121.     } 
  122.     template<class K, class V> RBTreeNode<K, V>* RedBlackTree<K
  123. , V>::getSibling(RBTreeNode<K, V>* pNode) 
  124.     { 
  125.         if (pNode == NULL || pNode->m_pParent == NULL) return NULL; 
  126.         if (pNode == pNode->m_pParent->m_pLChild) 
  127.             return pNode->m_pParent->m_pRChild; 
  128.         else 
  129.             return pNode->m_pParent->m_pLChild; 
  130.     } 
  131.  
  132.     template <class K, class V> void RedBlackTree<K, V>::rotateLeft(RBTreeNode<K, V>* pNode) 
  133.     { 
  134.         if (pNode == NULL || pNode->m_pRChild == NULL) 
  135.             return; 
  136.         else 
  137.         { 
  138.             RBTreeNode<K,V>* pTemp = pNode->m_pRChild; 
  139.             pNode->m_pRChild = pTemp->m_pLChild; 
  140.             if (pTemp->m_pLChild) 
  141.                 pTemp->m_pLChild->m_pParent = pNode; 
  142.             if (pNode == m_pRoot) 
  143.             { 
  144.                 m_pRoot = pTemp; 
  145.                 pTemp->m_pParent = NULL; 
  146.             } 
  147.             else 
  148.             { 
  149.                 pTemp->m_pParent= pNode->m_pParent;        
  150.                 if (pNode == pNode->m_pParent->m_pLChild)  
  151.                 {  
  152.                     pNode->m_pParent->m_pLChild = pTemp;  
  153.                 }  
  154.                 else  
  155.                 {  
  156.                     pNode->m_pParent->m_pRChild = pTemp;  
  157.                 }  
  158.             } 
  159.             pTemp->m_pLChild = pNode; 
  160.             pNode->m_pParent = pTemp; 
  161.         } 
  162.     } 
  163.     template <class K, class V> void RedBlackTree<K
  164. , V>::rotateRight(RBTreeNode<K, V>* pNode) 
  165.     { 
  166.         if (pNode == NULL || pNode->m_pLChild == NULL) 
  167.             return; 
  168.         else 
  169.         { 
  170.             RBTreeNode<K,V>* pTemp = pNode->m_pLChild; 
  171.             pNode->m_pLChild = pTemp->m_pRChild; 
  172.             if (pTemp->m_pRChild) 
  173.                 pTemp->m_pRChild->m_pParent = pNode; 
  174.             if (pNode == m_pRoot) 
  175.             { 
  176.                 m_pRoot = pTemp; 
  177.                 pTemp->m_pParent = NULL; 
  178.             } 
  179.             else 
  180.             { 
  181.                 //update the parent 
  182.                 pTemp->m_pParent= pNode->m_pParent;        
  183.                 if (pNode == pNode->m_pParent->m_pLChild)  
  184.                 {  
  185.                     pNode->m_pParent->m_pLChild = pTemp;  
  186.                 }  
  187.                 else  
  188.                 {  
  189.                     pNode->m_pParent->m_pRChild = pTemp;  
  190.                 }            
  191.             } 
  192.             pTemp->m_pRChild = pNode; 
  193.             pNode->m_pParent = pTemp; 
  194.         } 
  195.     } 
  196.     template <class K, class V> e_return RedBlackTree<K
  197. , V>::insert(const K& key, const V& value) 
  198.     { 
  199.         RBTreeNode<K, V>* pTemp = m_pRoot;  
  200.         RBTreeNode<K, V>* pParent = NULL;  
  201.         // init the new node here 
  202.         RBTreeNode<K, V>* pNew = new RBTreeNode<K, V>(key, value); 
  203.         pNew->color = red; 
  204.         pNew->m_pLChild = m_pSentinel; 
  205.         pNew->m_pRChild = m_pSentinel; 
  206.         // find the insert point 
  207.         while (pTemp != m_pSentinel)  
  208.         {  
  209.             pParent = pTemp;  
  210.             if (pTemp->key == key)  
  211.             {  
  212.                 delete pNew; 
  213.                 return e_duplicate;  
  214.             }  
  215.             pTemp = pTemp->key > key ? pTemp->m_pLChild: pTemp->m_pRChild;         
  216.         } 
  217.         if (m_pRoot == m_pSentinel)  
  218.         {  
  219.             m_pRoot = pNew; 
  220.             m_pRoot->m_pParent = NULL; 
  221.         }  
  222.         else  
  223.         {  
  224.             pNew->m_pParent = pParent; 
  225.             if ( pParent->key > key )  
  226.             {  
  227.                 pParent->m_pLChild= pNew;  
  228.             }  
  229.             else  
  230.             {  
  231.                 pParent->m_pRChild= pNew;  
  232.             }     
  233.         } 
  234.         insertFixup(pNew); 
  235.         //      insertCase1(pNew); 
  236. #ifdef MY_DEBUG      
  237.         assert(checkCorrectNess()); 
  238. #endif//MY_DEBUG 
  239.         return e_success; 
  240.     } 
  241.     template <class K, class V> void RedBlackTree<K
  242. ,V>::insertFixup(RBTreeNode<K, V>* pNode) 
  243.     { 
  244.         if (pNode == NULL) return; // impossible actually. 
  245.         RBTreeNode<K,V>* pUncle = m_pSentinel;  
  246.         RBTreeNode<K,V>* pGrandParent = NULL; 
  247.         while (pNode != m_pRoot && red == pNode->m_pParent->color)  
  248.         { 
  249.             pUncle = getUncle(pNode); 
  250.             pGrandParent = getGrandParent(pNode); 
  251.             if (pUncle != m_pSentinel && pUncle->color == red) 
  252.             { 
  253.                 pNode->m_pParent->color = black; 
  254.                 pUncle->color = black; 
  255.                 pGrandParent->color = red; 
  256.                 pNode = pGrandParent; 
  257.             } 
  258.             else 
  259.             { 
  260.                 if (pNode->m_pParent == pGrandParent->m_pLChild)     
  261.                 { 
  262.                     if (pNode == pNode->m_pParent->m_pRChild) 
  263.                     { 
  264.                         pNode = pNode->m_pParent; 
  265.                         rotateLeft(pNode); 
  266.                     } 
  267.                     pNode->m_pParent->color = black; 
  268.                     pGrandParent->color = red; 
  269.                     rotateRight(pGrandParent); 
  270.                 } 
  271.                 else 
  272.                 { 
  273.                     if (pNode == pNode->m_pParent->m_pLChild) 
  274.                     { 
  275.                         pNode = pNode->m_pParent; 
  276.                         rotateRight(pNode); 
  277.                     } 
  278.                     pNode->m_pParent->color = black; 
  279.                     pGrandParent->color = red; 
  280.                     rotateLeft(pGrandParent); 
  281.                 } 
  282.             } 
  283.         } 
  284.         m_pRoot->color = black;  
  285.     } 
  286.     template <class K, class V> e_return RedBlackTree<K,V>::remove(const K& key) 
  287.     { 
  288.         // currently we won't use the  
  289.         if (!m_pRoot) return e_empty; 
  290.         RBTreeNode<K,V>* pd = m_pRoot;
  291. // pd means pointer to the node deleted (with the same data with param:data) 
  292.         while (pd != m_pSentinel) 
  293.         { 
  294.             if (pd->key > key) 
  295.                 pd = pd->m_pLChild; 
  296.             else if (pd->key < key) 
  297.                 pd = pd->m_pRChild; 
  298.             else 
  299.                 break; // equal so we find it!!! 
  300.         } 
  301.         if (pd == m_pSentinel) //haven't find it 
  302.             return e_not_found; 
  303.         // delete is not the real node to delete, but find a sub to replace and remove the sub 
  304.         RBTreeNode<K,V>* pSub = NULL; // pSub is the really node to be sub 
  305.         // we can either find the max left child or min right child to sub 
  306.         // let's choose max left child here 
  307.         if (pd->m_pLChild == m_pSentinel && pd->m_pRChild == m_pSentinel) 
  308.             pSub = pd; 
  309.         else if (pd->m_pLChild == m_pSentinel) 
  310.             pSub = pd->m_pRChild; 
  311.         else if (pd->m_pRChild == m_pSentinel) 
  312.             pSub = pd->m_pLChild; 
  313.         else 
  314.         { 
  315.             pSub = pd->m_pLChild; 
  316.             // let's find the max left child 
  317.             while (pSub->m_pRChild != m_pSentinel) 
  318.             { 
  319.                 pSub = pSub->m_pRChild; 
  320.             } 
  321.         } 
  322.         // replace the pd data with pSub's 
  323.         if (pd != pSub) 
  324.         { 
  325.             pd->key = pSub->key; 
  326.             pd->value = pSub->value; 
  327.         } 
  328.         // then find the child of sub and replace with sub 
  329.         RBTreeNode<K,V>* pSubChild = pSub->m_pRChild
  330.  != m_pSentinel ? pSub->m_pRChild: pSub->m_pLChild; 
  331.         if (pSub->m_pParent) 
  332.         { 
  333.             if (pSub == pSub->m_pParent->m_pLChild) 
  334.                 pSub->m_pParent->m_pLChild = pSubChild; 
  335.             else 
  336.                 pSub->m_pParent->m_pRChild = pSubChild; 
  337.         } 
  338.         else 
  339.         { 
  340.             m_pRoot = pSubChild; 
  341.         } 
  342.         //this may change the sentinel's parent to not-null value, will change to NULL later 
  343.         pSubChild->m_pParent = pSub->m_pParent; 
  344.         if (pSub->color == black) 
  345.             removeFixup(pSubChild); 
  346.         if (pSub) 
  347.         { 
  348.             delete pSub; 
  349.             pSub = NULL; 
  350.         } 
  351.         // rollback sentinel's parent to NULL; 
  352.         m_pSentinel->m_pParent = NULL; 
  353. #ifdef MY_DEBUG 
  354.         assert(checkCorrectNess()); 
  355. #endif //MY_DEBUG 
  356.         return e_success; 
  357.     } 
  358.     template <class K, class V> void RedBlackTree<K
  359. ,V>::removeFixup(RBTreeNode<K,V>* pNode) 
  360.     { 
  361.         RBTreeNode<K,V>* pSibling = NULL; 
  362.         while ((pNode != m_pRoot) && (pNode->color == black)) 
  363.         { 
  364.             pSibling = getSibling(pNode); 
  365.             if (pNode == pNode->m_pParent->m_pLChild) // left child node 
  366.             { 
  367.                 if (pSibling->color == red) 
  368.                 { 
  369.                     // case 1, can change to case 2, 3, 4 
  370.                     pNode->m_pParent->color = red; 
  371.                     pSibling->color = black; 
  372.                     rotateLeft(pNode->m_pParent); 
  373.                     // change to new sibling,  
  374.                     pSibling = pNode->m_pParent->m_pRChild; 
  375.                 } 
  376.                 // case 2; 
  377.                 if ((black == pSibling->m_pLChild->color)
  378.  && (black == pSibling->m_pRChild->color))  
  379.                 {  
  380.                     pSibling->color = red;  
  381.                     pNode = pNode->m_pParent;  
  382.                 } 
  383.                 else 
  384.                 { 
  385.                     if (black == pSibling->m_pRChild->color)  
  386.                     {  
  387.                         pSibling->color = red;  
  388.                         pSibling->m_pLChild->color = black;  
  389.                         rotateRight(pSibling);  
  390.                         pSibling = pNode->m_pParent->m_pRChild;  
  391.                     } 
  392.                     pSibling->color = pNode->m_pParent->color; 
  393.                     pNode->m_pParent->color = black; 
  394.                     pSibling->m_pRChild->color = black; 
  395.                     rotateLeft(pNode->m_pParent); 
  396.                     break;  
  397.                 } 
  398.             } 
  399.             else 
  400.             { 
  401.                 if (pSibling->color == red) 
  402.                 { 
  403.                     // case 1, can change to case 2, 3, 4 
  404.                     pNode->m_pParent->color = red; 
  405.                     pSibling->color = black; 
  406.                     rotateRight(pNode->m_pParent); 
  407.                     // change to new sibling,  
  408.                     pSibling = pNode->m_pParent->m_pLChild; 
  409.                 } 
  410.                 // case 2; 
  411.                 if ((black == pSibling->m_pLChild->color)
  412.  && (black == pSibling->m_pRChild->color))  
  413.                 {  
  414.                     pSibling->color = red;  
  415.                     pNode = pNode->m_pParent;  
  416.                 } 
  417.                 else 
  418.                 { 
  419.                     if (black == pSibling->m_pLChild->color)  
  420.                     {  
  421.                         pSibling->color = red;  
  422.                         pSibling->m_pRChild->color = black;  
  423.                         rotateLeft(pSibling);  
  424.                         pSibling = pNode->m_pParent->m_pLChild;  
  425.                     } 
  426.                     pSibling->color = pNode->m_pParent->color; 
  427.                     pNode->m_pParent->color = black; 
  428.                     pSibling->m_pLChild->color = black; 
  429.                     rotateRight(pNode->m_pParent); 
  430.                     break;  
  431.                 } 
  432.             } 
  433.         } 
  434.         pNode->color = black; 
  435.     } 
  436.  
  437.     template <class K, class V> e_return RedBlackTree<K
  438. ,V>::search(const K& key, V& value) // value as output 
  439.     { 
  440.         if (!m_pRoot) return e_empty; 
  441.          
  442.         RBTreeNode<K,V>* pTemp = m_pRoot; 
  443.         while (pTemp != m_pSentinel) 
  444.         { 
  445.             if (pTemp->key < key) 
  446.                 pTemp = pTemp->m_pRChild; 
  447.             else if (pTemp->key > key) 
  448.                 pTemp = pTemp->m_pLChild; 
  449.             else 
  450.                 break; 
  451.         } 
  452.         if (pTemp != m_pSentinel) 
  453.         { 
  454.             //find it now! 
  455.             value = pTemp->value; 
  456.             return e_success; 
  457.         } 
  458.         else 
  459.         { 
  460.             return e_not_found; 
  461.         } 
  462.     } 
  463. #ifdef MY_DEBUG 
  464.     template <class K, class V>bool RedBlackTree<K,V>::checkCorrectNess() 
  465.     { 
  466.         if (!m_pRoot) 
  467.             return true; 
  468.         bool bRet = true; 
  469.         // check if the root color is black 
  470.         if (m_pRoot && m_pRoot->color == red) 
  471.             bRet = false; 
  472.         // check red node with black child 
  473.         std::queue< RBTreeNode<K,V>* > oQueue;                                    
  474.         oQueue.push( m_pRoot ); 
  475.         int nCurLevelCount = 1; 
  476.         int length = -1; 
  477.         while (true) 
  478.         { 
  479.             int nNextLevelCount     = 0;        
  480.             while (nCurLevelCount) 
  481.             { 
  482.                 RBTreeNode<K,V>* pNode = oQueue.front(); 
  483.                 nCurLevelCount -- ; 
  484.                 if(pNode->color == red) 
  485.                 { 
  486.                     // child color is black 
  487.                     if ((pNode->m_pLChild && pNode->m_pLChild->color == red) || 
  488.                         (pNode->m_pRChild && pNode->m_pRChild->color == red)) 
  489.                     { 
  490.                         bRet = false; 
  491.                         break; 
  492.                     }     
  493.                 } 
  494.                 if ( !pNode->m_pLChild && !pNode->m_pRChild) 
  495.                 { 
  496.                     // this is the leaf node, check the path root 
  497.                     int len = 0; 
  498.                     RBTreeNode<K,V>* pTemp = pNode; 
  499.                     while (pTemp->m_pParent) 
  500.                     { 
  501.                         if (pTemp->color == black) 
  502.                             len ++ ; 
  503.                         pTemp = pTemp->m_pParent; 
  504.                     } 
  505.                     if (length == -1) 
  506.                         length = len; 
  507.                     else 
  508.                     { 
  509.                         if (len != length) 
  510.                         { 
  511.                             bRet = false; 
  512.                             break; 
  513.                         } 
  514.                     } 
  515.                 } 
  516.                 if (pNode->m_pLChild) 
  517.                 { 
  518.                     oQueue.push( pNode->m_pLChild ); 
  519.                     nNextLevelCount++;      
  520.                 } 
  521.                 if (pNode->m_pRChild) 
  522.                 { 
  523.                     oQueue.push( pNode->m_pRChild ); 
  524.                     nNextLevelCount++;      
  525.                 } 
  526.                 oQueue.pop(); 
  527.             } 
  528.             if (!bRet) 
  529.                 break; 
  530.             nCurLevelCount = nNextLevelCount; 
  531.             if (!nCurLevelCount) 
  532.                 break; 
  533.         } 
  534.         return bRet; 
  535.     } 
  536. #endif //MY_DEBUG 
  537. } 

 

(hhygcy)
本站文章除注明转载外，均为本站原创或编译欢迎任何形式的转载，但请务必注明出处，尊重他人劳动，同学习共成长。转载请注明：文章转载自：罗索实验室 [http://www.rosoo.net/a/201207/16151.html]
本文出处：CSDN博客　作者：hhygcy 原文
顶一下
(5)
100%
踩一下
(0)
0%
------分隔线----------------------------
相关文章
发表评论
请自觉遵守互联网相关的政策法规，严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
最新评论 进入详细评论页>>
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容
热点内容