在实现之前网上浏览了一下,看到很多人都有自己的实现.主要的实现方式都是受了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的代码用以检查平衡度的正确性,至少可以避免明显错误的尴尬:)
最后给出了所有的代码:
- #pragma once
- #ifdef MY_DEBUG
- #include <queue>
- #include "assert.h"
- #endif //MY_DEBUG
- namespace ScanbuyLib{
- enum rg_color { black, red } ;
- enum e_balance { left_higher, equal_height, right_higher };
- enum e_return { e_success, e_fail, e_empty, e_duplicate, e_not_found };
- enum e_order { e_preorder, e_inorder, e_postorder };
- template <class K, class V> class RBTreeNode
- {
- public:
- RBTreeNode(rg_color color = black);
- RBTreeNode(const K& key, const V& value, rg_color color= black);
- public:
- RBTreeNode<K,V>* m_pRChild;
- RBTreeNode<K,V>* m_pLChild;
- RBTreeNode<K,V>* m_pParent;
- K key;
- V value;
- rg_color color;
- };
- template<class K, class V> RBTreeNode<K, V>::RBTreeNode(rg_color color)
- {
- m_pRChild = NULL;
- m_pLChild = NULL;
- m_pParent = NULL;
-
-
- this->color = color;
- }
- template<class K, class V>RBTreeNode<K, V>::RBTreeNode(const K& key
- , const V& value, rg_color color)
- {
- m_pRChild = NULL;
- m_pLChild = NULL;
- m_pParent = NULL;
- this->key = key;
- this->value = value;
- this->color = color;
- }
- template <class K, class V> class RedBlackTree
- {
- public:
- RedBlackTree();
- ~RedBlackTree();
- e_return insert(const K& key, const V& value);
- e_return remove(const K& key);
- e_return search(const K& key, V& value);
- private:
-
- void destroy(RBTreeNode<K, V>* pNode);
-
- RedBlackTree(const RedBlackTree&);
- RedBlackTree& operator = (const RedBlackTree& other);
-
- RBTreeNode<K, V>* getGrandParent(RBTreeNode<K, V>* pNode);
- RBTreeNode<K, V>* getUncle(RBTreeNode<K, V>* pNode);
- RBTreeNode<K, V>* getSibling(RBTreeNode<K, V>* pNode);
- #ifdef MY_DEBUG
- bool checkCorrectNess();
- #endif //MY_DEBUG
- void insertFixup(RBTreeNode<K, V>* pNode);
- void removeFixup(RBTreeNode<K, V>* pNode);
- void rotateLeft (RBTreeNode<K, V>* pNode);
- void rotateRight(RBTreeNode<K, V>* pNode);
- RBTreeNode<K, V>* m_pRoot;
- RBTreeNode<K, V>* m_pSentinel;
- };
-
- template <class K, class V>RedBlackTree<K, V>::RedBlackTree()
- {
-
- m_pSentinel = new RBTreeNode<K,V>();
- m_pSentinel->m_pLChild = NULL;
- m_pSentinel->m_pRChild = NULL;
- m_pSentinel->m_pParent = NULL;
- m_pSentinel->color = black;
- m_pRoot = m_pSentinel;
- }
- template <class K, class V>RedBlackTree<K, V>::~RedBlackTree()
- {
-
- destroy(m_pRoot);
- if (m_pSentinel)
- {
- delete m_pSentinel;
- m_pSentinel = NULL;
- }
- }
-
- template <class K, class V> void RedBlackTree<K, V>::destroy(RBTreeNode<K, V>* pNode)
- {
- if (pNode != NULL && pNode != m_pSentinel)
- {
- destroy(pNode->m_pLChild);
- destroy(pNode->m_pRChild);
- delete pNode;
- pNode = NULL;
- }
- }
- template <class K, class V> RBTreeNode<K, V>* RedBlackTree<K
- , V>::getGrandParent(RBTreeNode<K, V>* pNode)
- {
- if (pNode && pNode->m_pParent)
- return pNode->m_pParent->m_pParent;
- else
- return NULL;
- }
- template <class K, class V> RBTreeNode<K, V>* RedBlackTree<K
- , V>::getUncle(RBTreeNode<K, V>* pNode)
- {
- RBTreeNode<K, V>* pTemp = getGrandParent(pNode);
- if (pTemp == NULL)
- return NULL;
- if (pNode->m_pParent == pTemp->m_pLChild)
- return pTemp->m_pRChild;
- else
- return pTemp->m_pLChild;
- }
- template<class K, class V> RBTreeNode<K, V>* RedBlackTree<K
- , V>::getSibling(RBTreeNode<K, V>* pNode)
- {
- if (pNode == NULL || pNode->m_pParent == NULL) return NULL;
- if (pNode == pNode->m_pParent->m_pLChild)
- return pNode->m_pParent->m_pRChild;
- else
- return pNode->m_pParent->m_pLChild;
- }
-
- template <class K, class V> void RedBlackTree<K, V>::rotateLeft(RBTreeNode<K, V>* pNode)
- {
- if (pNode == NULL || pNode->m_pRChild == NULL)
- return;
- else
- {
- RBTreeNode<K,V>* pTemp = pNode->m_pRChild;
- pNode->m_pRChild = pTemp->m_pLChild;
- if (pTemp->m_pLChild)
- pTemp->m_pLChild->m_pParent = pNode;
- if (pNode == m_pRoot)
- {
- m_pRoot = pTemp;
- pTemp->m_pParent = NULL;
- }
- else
- {
- pTemp->m_pParent= pNode->m_pParent;
- if (pNode == pNode->m_pParent->m_pLChild)
- {
- pNode->m_pParent->m_pLChild = pTemp;
- }
- else
- {
- pNode->m_pParent->m_pRChild = pTemp;
- }
- }
- pTemp->m_pLChild = pNode;
- pNode->m_pParent = pTemp;
- }
- }
- template <class K, class V> void RedBlackTree<K
- , V>::rotateRight(RBTreeNode<K, V>* pNode)
- {
- if (pNode == NULL || pNode->m_pLChild == NULL)
- return;
- else
- {
- RBTreeNode<K,V>* pTemp = pNode->m_pLChild;
- pNode->m_pLChild = pTemp->m_pRChild;
- if (pTemp->m_pRChild)
- pTemp->m_pRChild->m_pParent = pNode;
- if (pNode == m_pRoot)
- {
- m_pRoot = pTemp;
- pTemp->m_pParent = NULL;
- }
- else
- {
-
- pTemp->m_pParent= pNode->m_pParent;
- if (pNode == pNode->m_pParent->m_pLChild)
- {
- pNode->m_pParent->m_pLChild = pTemp;
- }
- else
- {
- pNode->m_pParent->m_pRChild = pTemp;
- }
- }
- pTemp->m_pRChild = pNode;
- pNode->m_pParent = pTemp;
- }
- }
- template <class K, class V> e_return RedBlackTree<K
- , V>::insert(const K& key, const V& value)
- {
- RBTreeNode<K, V>* pTemp = m_pRoot;
- RBTreeNode<K, V>* pParent = NULL;
-
- RBTreeNode<K, V>* pNew = new RBTreeNode<K, V>(key, value);
- pNew->color = red;
- pNew->m_pLChild = m_pSentinel;
- pNew->m_pRChild = m_pSentinel;
-
- while (pTemp != m_pSentinel)
- {
- pParent = pTemp;
- if (pTemp->key == key)
- {
- delete pNew;
- return e_duplicate;
- }
- pTemp = pTemp->key > key ? pTemp->m_pLChild: pTemp->m_pRChild;
- }
- if (m_pRoot == m_pSentinel)
- {
- m_pRoot = pNew;
- m_pRoot->m_pParent = NULL;
- }
- else
- {
- pNew->m_pParent = pParent;
- if ( pParent->key > key )
- {
- pParent->m_pLChild= pNew;
- }
- else
- {
- pParent->m_pRChild= pNew;
- }
- }
- insertFixup(pNew);
-
- #ifdef MY_DEBUG
- assert(checkCorrectNess());
- #endif//MY_DEBUG
- return e_success;
- }
- template <class K, class V> void RedBlackTree<K
- ,V>::insertFixup(RBTreeNode<K, V>* pNode)
- {
- if (pNode == NULL) return;
- RBTreeNode<K,V>* pUncle = m_pSentinel;
- RBTreeNode<K,V>* pGrandParent = NULL;
- while (pNode != m_pRoot && red == pNode->m_pParent->color)
- {
- pUncle = getUncle(pNode);
- pGrandParent = getGrandParent(pNode);
- if (pUncle != m_pSentinel && pUncle->color == red)
- {
- pNode->m_pParent->color = black;
- pUncle->color = black;
- pGrandParent->color = red;
- pNode = pGrandParent;
- }
- else
- {
- if (pNode->m_pParent == pGrandParent->m_pLChild)
- {
- if (pNode == pNode->m_pParent->m_pRChild)
- {
- pNode = pNode->m_pParent;
- rotateLeft(pNode);
- }
- pNode->m_pParent->color = black;
- pGrandParent->color = red;
- rotateRight(pGrandParent);
- }
- else
- {
- if (pNode == pNode->m_pParent->m_pLChild)
- {
- pNode = pNode->m_pParent;
- rotateRight(pNode);
- }
- pNode->m_pParent->color = black;
- pGrandParent->color = red;
- rotateLeft(pGrandParent);
- }
- }
- }
- m_pRoot->color = black;
- }
- template <class K, class V> e_return RedBlackTree<K,V>::remove(const K& key)
- {
-
- if (!m_pRoot) return e_empty;
- RBTreeNode<K,V>* pd = m_pRoot;
-
- while (pd != m_pSentinel)
- {
- if (pd->key > key)
- pd = pd->m_pLChild;
- else if (pd->key < key)
- pd = pd->m_pRChild;
- else
- break;
- }
- if (pd == m_pSentinel)
- return e_not_found;
-
- RBTreeNode<K,V>* pSub = NULL;
-
-
- if (pd->m_pLChild == m_pSentinel && pd->m_pRChild == m_pSentinel)
- pSub = pd;
- else if (pd->m_pLChild == m_pSentinel)
- pSub = pd->m_pRChild;
- else if (pd->m_pRChild == m_pSentinel)
- pSub = pd->m_pLChild;
- else
- {
- pSub = pd->m_pLChild;
-
- while (pSub->m_pRChild != m_pSentinel)
- {
- pSub = pSub->m_pRChild;
- }
- }
-
- if (pd != pSub)
- {
- pd->key = pSub->key;
- pd->value = pSub->value;
- }
-
- RBTreeNode<K,V>* pSubChild = pSub->m_pRChild
- != m_pSentinel ? pSub->m_pRChild: pSub->m_pLChild;
- if (pSub->m_pParent)
- {
- if (pSub == pSub->m_pParent->m_pLChild)
- pSub->m_pParent->m_pLChild = pSubChild;
- else
- pSub->m_pParent->m_pRChild = pSubChild;
- }
- else
- {
- m_pRoot = pSubChild;
- }
-
- pSubChild->m_pParent = pSub->m_pParent;
- if (pSub->color == black)
- removeFixup(pSubChild);
- if (pSub)
- {
- delete pSub;
- pSub = NULL;
- }
-
- m_pSentinel->m_pParent = NULL;
- #ifdef MY_DEBUG
- assert(checkCorrectNess());
- #endif //MY_DEBUG
- return e_success;
- }
- template <class K, class V> void RedBlackTree<K
- ,V>::removeFixup(RBTreeNode<K,V>* pNode)
- {
- RBTreeNode<K,V>* pSibling = NULL;
- while ((pNode != m_pRoot) && (pNode->color == black))
- {
- pSibling = getSibling(pNode);
- if (pNode == pNode->m_pParent->m_pLChild)
- {
- if (pSibling->color == red)
- {
-
- pNode->m_pParent->color = red;
- pSibling->color = black;
- rotateLeft(pNode->m_pParent);
-
- pSibling = pNode->m_pParent->m_pRChild;
- }
-
- if ((black == pSibling->m_pLChild->color)
- && (black == pSibling->m_pRChild->color))
- {
- pSibling->color = red;
- pNode = pNode->m_pParent;
- }
- else
- {
- if (black == pSibling->m_pRChild->color)
- {
- pSibling->color = red;
- pSibling->m_pLChild->color = black;
- rotateRight(pSibling);
- pSibling = pNode->m_pParent->m_pRChild;
- }
- pSibling->color = pNode->m_pParent->color;
- pNode->m_pParent->color = black;
- pSibling->m_pRChild->color = black;
- rotateLeft(pNode->m_pParent);
- break;
- }
- }
- else
- {
- if (pSibling->color == red)
- {
-
- pNode->m_pParent->color = red;
- pSibling->color = black;
- rotateRight(pNode->m_pParent);
-
- pSibling = pNode->m_pParent->m_pLChild;
- }
-
- if ((black == pSibling->m_pLChild->color)
- && (black == pSibling->m_pRChild->color))
- {
- pSibling->color = red;
- pNode = pNode->m_pParent;
- }
- else
- {
- if (black == pSibling->m_pLChild->color)
- {
- pSibling->color = red;
- pSibling->m_pRChild->color = black;
- rotateLeft(pSibling);
- pSibling = pNode->m_pParent->m_pLChild;
- }
- pSibling->color = pNode->m_pParent->color;
- pNode->m_pParent->color = black;
- pSibling->m_pLChild->color = black;
- rotateRight(pNode->m_pParent);
- break;
- }
- }
- }
- pNode->color = black;
- }
-
- template <class K, class V> e_return RedBlackTree<K
- ,V>::search(const K& key, V& value)
- {
- if (!m_pRoot) return e_empty;
-
- RBTreeNode<K,V>* pTemp = m_pRoot;
- while (pTemp != m_pSentinel)
- {
- if (pTemp->key < key)
- pTemp = pTemp->m_pRChild;
- else if (pTemp->key > key)
- pTemp = pTemp->m_pLChild;
- else
- break;
- }
- if (pTemp != m_pSentinel)
- {
-
- value = pTemp->value;
- return e_success;
- }
- else
- {
- return e_not_found;
- }
- }
- #ifdef MY_DEBUG
- template <class K, class V>bool RedBlackTree<K,V>::checkCorrectNess()
- {
- if (!m_pRoot)
- return true;
- bool bRet = true;
-
- if (m_pRoot && m_pRoot->color == red)
- bRet = false;
-
- std::queue< RBTreeNode<K,V>* > oQueue;
- oQueue.push( m_pRoot );
- int nCurLevelCount = 1;
- int length = -1;
- while (true)
- {
- int nNextLevelCount = 0;
- while (nCurLevelCount)
- {
- RBTreeNode<K,V>* pNode = oQueue.front();
- nCurLevelCount -- ;
- if(pNode->color == red)
- {
-
- if ((pNode->m_pLChild && pNode->m_pLChild->color == red) ||
- (pNode->m_pRChild && pNode->m_pRChild->color == red))
- {
- bRet = false;
- break;
- }
- }
- if ( !pNode->m_pLChild && !pNode->m_pRChild)
- {
-
- int len = 0;
- RBTreeNode<K,V>* pTemp = pNode;
- while (pTemp->m_pParent)
- {
- if (pTemp->color == black)
- len ++ ;
- pTemp = pTemp->m_pParent;
- }
- if (length == -1)
- length = len;
- else
- {
- if (len != length)
- {
- bRet = false;
- break;
- }
- }
- }
- if (pNode->m_pLChild)
- {
- oQueue.push( pNode->m_pLChild );
- nNextLevelCount++;
- }
- if (pNode->m_pRChild)
- {
- oQueue.push( pNode->m_pRChild );
- nNextLevelCount++;
- }
- oQueue.pop();
- }
- if (!bRet)
- break;
- nCurLevelCount = nNextLevelCount;
- if (!nCurLevelCount)
- break;
- }
- return bRet;
- }
- #endif //MY_DEBUG
- }
(hhygcy) |