红黑树的插入，删除简单实现
主要理解的难点在删除的实现，当删除节点存在左右子节点时，需选择右侧后续节点，然后替换两个节点，当被替换节点是叶节点时，需要重新平衡该树，此时以空节点染黑代替进行平衡操作，再做各种变换，与书上的图操作相似， 详见“[balance]”
#ifndef CRBTREE_H #define CRBTREE_H #include <cstddef> using namespace std; enum NodeColor{ colorred, colorblack }; template <class T> struct RBNode { NodeColor color; RBNode *leftnode; RBNode *rightnode; RBNode *parentnode; T obj; }; template <class T> RBNode<T> *__InitNode(const T& obj) { RBNode<T> *rbnode = new RBNode<T>(); rbnode->color = colorred; rbnode->leftnode = NULL; rbnode->rightnode = NULL; rbnode->parentnode = NULL; rbnode->obj = obj; return rbnode; } template <class T> class CRBTree { public: typedef RBNode<T> NodeType; typedef NodeType* NodeTypePtr; typedef T value_type; CRBTree(){ headnode = NULL; } ~CRBTree(){ } bool Empty() { return headnode == NULL; } void Insert(const value_type &obj) { NodeType *newnode = __InitNode(obj); if (Empty()) { newnode->color = colorblack; headnode = newnode; } else { _InsertNode(newnode); if (newnode->parentnode->color == colorred) { _Recolor(newnode); } } } void Erase(const value_type &obj) { NodeType *_EraseNode = _FindNode(headnode, obj); if (_EraseNode) { NodeTypePtr _Fixnode; // the node to recolor as needed NodeTypePtr _Fixnodeparent; // parent of _Fixnode (which may be nil) NodeTypePtr _Pnode = _EraseNode; if (_Pnode->leftnode == NULL) _Fixnode = _Pnode->rightnode; // stitch up right subtree else if (_Pnode->rightnode == NULL) _Fixnode = _Pnode->leftnode; // stitch up left subtree else { // two subtrees, must lift successor node to replace erased _Pnode = (++iter(_EraseNode)).data(); // _Pnode is successor node _Fixnode = _Pnode->rightnode; // _Fixnode is only subtree } if (_Pnode == _EraseNode) { // at most one subtree, relink it,only black parent link one red child _Fixnodeparent = _EraseNode->parentnode; if (_Fixnode != NULL) _Fixnode->parentnode = _Fixnodeparent; if (headnode == _EraseNode) headnode = _Fixnode; else if (_Fixnodeparent->leftnode == _EraseNode) _Fixnodeparent->leftnode = _Fixnode; else _Fixnodeparent->rightnode = _Fixnode; } else { //two subtrees, find the successor node and swap with the Erasenode _EraseNode->leftnode->parentnode = _Pnode; _Pnode->leftnode = _EraseNode->leftnode; if (_EraseNode->rightnode == _Pnode) { _Fixnodeparent = _Pnode; } else { _Fixnodeparent = _Pnode->parentnode; if (_Fixnode != NULL) _Fixnode->parentnode = _Fixnodeparent; _Fixnodeparent->leftnode = _Fixnode; _Pnode->rightnode = _EraseNode->rightnode; _EraseNode->rightnode->parentnode = _Pnode; } if (headnode == _EraseNode) headnode = _Pnode; else if (_EraseNode->parentnode->leftnode == _EraseNode) _EraseNode->parentnode->leftnode = _Pnode; else _EraseNode->parentnode->rightnode = _Pnode; _Pnode->parentnode = _EraseNode->parentnode; //swap color NodeColor color = _Pnode->color; _Pnode->color = _EraseNode->color; _EraseNode->color = color; } if (_EraseNode->color == colorblack) { if (_Fixnode != NULL) _Fixnode->color = colorblack; else { //[balance] while (_Fixnode != headnode && (_Fixnode == NULL || _Fixnode->color == colorblack)) { if (_Fixnode == _Fixnodeparent->leftnode) { NodeTypePtr _Unclenode = _Fixnodeparent->rightnode; if (_Unclenode->color == colorred) { _Unclenode->color = colorblack; _Fixnodeparent->color = colorred; _LeftRotate(_Fixnodeparent); _Unclenode = _Fixnodeparent->rightnode; } if ((_Unclenode->leftnode == NULL || _Unclenode->leftnode->color == colorblack) && (_Unclenode->rightnode == NULL || _Unclenode->rightnode->color == colorblack)) { _Unclenode->color = colorred; _Fixnode = _Fixnodeparent; _Fixnodeparent = _Fixnodeparent->parentnode; } else { if (_Unclenode->rightnode == 0 || _Unclenode->rightnode->color == colorblack) { if (_Unclenode->leftnode != NULL) _Unclenode->leftnode->color = colorblack; _Unclenode->color = colorred; _RightRotate(_Unclenode); _Unclenode = _Fixnodeparent->rightnode; } _Unclenode->color = _Fixnodeparent->color; _Fixnodeparent->color = colorblack; if (_Unclenode->rightnode != NULL) _Unclenode->rightnode->color = colorblack; _LeftRotate(_Fixnodeparent); break; } } else { NodeTypePtr _UncleNode = _Fixnodeparent->leftnode; if (_UncleNode->color == colorred) { _UncleNode->color = colorblack; _Fixnodeparent->color = colorred; _RightRotate(_Fixnodeparent); _UncleNode = _Fixnodeparent->leftnode; } if ((_UncleNode->rightnode == NULL ||_UncleNode->rightnode->color == colorblack) && (_UncleNode->leftnode == NULL || _UncleNode->leftnode->color == colorblack)) { _UncleNode->color = colorred; _Fixnode = _Fixnodeparent; _Fixnodeparent = _Fixnodeparent->parentnode; } else { if (_UncleNode->leftnode == NULL || _UncleNode->leftnode->color == colorblack) { if (_UncleNode->rightnode) _UncleNode->rightnode->color = colorblack; _UncleNode->color = colorred; _LeftRotate(_UncleNode); _UncleNode = _Fixnodeparent->leftnode; } _UncleNode->color = _Fixnodeparent->color; _Fixnodeparent->color = colorblack; if (_UncleNode->leftnode) _UncleNode->leftnode->color = colorblack; _RightRotate(_Fixnodeparent); break; } } } if (_Fixnode) _Fixnode->color = colorblack; } } delete _EraseNode; } } class iter{ public: iter(NodeType *node) :_node(node) { } iter operator ++() { if (_node->rightnode) { _node = _node->rightnode; while(_node && _node->leftnode) { _node = _node->leftnode; } } else if (_node->parentnode == NULL) { _node = NULL; } else if (_node == _node->parentnode->leftnode) { _node = _node->parentnode; } else if (_node == _node->parentnode->rightnode) { NodeType *_parent = _node->parentnode; if (_parent->parentnode && _parent == _parent->parentnode->leftnode) { _node = _parent->parentnode; } else { _node = NULL; } } return *this; } bool operator == (const iter& other) { return _node == other._node; } bool operator != (const iter& other) { return _node != other._node; } NodeType* operator -> () const { return _node;} NodeType* data() const { return _node; } private: NodeType *_node; }; iter begin() { NodeType *_tnode = headnode; if (_tnode != NULL) { while(_tnode->leftnode) { _tnode = _tnode->leftnode; } } return iter(_tnode); } iter end() { return iter(NULL); } void clear() { _Erase(headnode); headnode = NULL; } private: NodeType *headnode; void _LeftRotate(NodeType *nodeA){ NodeType *nodeB = nodeA->rightnode; NodeType *nodeC = nodeB->leftnode; nodeA->rightnode = nodeC; if (nodeC) nodeC->parentnode = nodeA; nodeB->leftnode = nodeA; nodeB->parentnode = nodeA->parentnode; if (nodeA->parentnode == NULL) headnode = nodeB; else { if (nodeA->parentnode->leftnode == nodeA) nodeA->parentnode->leftnode = nodeB; else nodeA->parentnode->rightnode = nodeB; } nodeA->parentnode = nodeB; } void _RightRotate(NodeType *nodeA){ NodeType *nodeB = nodeA->leftnode; NodeType *nodeC = nodeB->rightnode; nodeA->leftnode = nodeC; if (nodeC) nodeC->parentnode = nodeA; nodeB->rightnode = nodeA; nodeB->parentnode = nodeA->parentnode; if (nodeA->parentnode == NULL) headnode = nodeB; else { if (nodeA->parentnode->leftnode == nodeA) nodeA->parentnode->leftnode = nodeB; else nodeA->parentnode->rightnode = nodeB; } nodeA->parentnode = nodeB; } void _InsertNode(NodeType *node) { NodeType *parent = headnode; do{ if (node->obj < parent->obj) { if (parent->leftnode == NULL) { parent->leftnode = node; node->parentnode = parent; break; } else parent = parent->leftnode; } else { if (parent->rightnode == NULL) { parent->rightnode = node; node->parentnode = parent; break; } else parent = parent->rightnode; } }while(1); } NodeType* _FindNode(NodeType *pNode,const value_type& obj) { NodeType *_node = pNode; do{ if (_node == NULL || _node->obj == obj) { return _node; } else if (_node->obj < obj) { return _FindNode(_node->rightnode, obj); } else { return _FindNode(_node->leftnode, obj); } }while(1); } void _Recolor(NodeType *node) { NodeType *_parent = node->parentnode; if (node == headnode) { node->color = colorblack; } else if (_parent->color == colorblack) { return; } else { NodeType *_grand = _parent->parentnode; if (_parent == _grand->leftnode) { NodeType *_uncle = _grand->rightnode; if (_uncle && _uncle->color == colorred) { _parent->color = colorblack; _uncle->color = colorblack; _grand->color = colorred; _Recolor(_grand); } else { if (node == _parent->rightnode) { node = node->parentnode; _LeftRotate(node); } node->parentnode->color = colorblack; node->parentnode->parentnode->color = colorred; _RightRotate(node->parentnode->parentnode); } } else { NodeType *_uncle = _grand->leftnode; if (_uncle && _uncle->color == colorred) { _parent->color = colorblack; _uncle->color = colorblack; _grand->color = colorred; _Recolor(_grand); } else { if (node == _parent->leftnode) { node = node->parentnode; _RightRotate(node); } node->parentnode->color = colorblack; node->parentnode->parentnode->color = colorred; _LeftRotate(node->parentnode->parentnode); } } } } void _Erase(NodeType *node) { for (NodeType *_Pnode = node; _Pnode != NULL; node = _Pnode) { // free subtrees, then node _Erase(_Pnode->rightnode); _Pnode = _Pnode->leftnode; delete node; } } }; #endif // CRBTREE_H测试代码：
#include <iostream> #include "rbtree.h" using namespace std; void printtree(CRBTree<int>& rbtree) { //check tree balance int blackdepth = 0; for ( CRBTree<int>::iter it = rbtree.begin(); it != rbtree.end(); ++it) { int branchdepth = 0; if (it->leftnode == NULL || it->rightnode == NULL) { branchdepth ++; RBNode<int>* node = it.data(); while (node != NULL) { if (node->color == colorblack) branchdepth++; node = node->parentnode; } if (blackdepth == 0) blackdepth = branchdepth; else if (blackdepth != branchdepth) cout << "RBTree is not balance now!\n"; } } for ( CRBTree<int>::iter it = rbtree.begin(); it != rbtree.end(); ++it) { cout << it->obj; const char *temp = (it->color==colorblack) ? "B" : "R"; cout << temp; if (it->leftnode != NULL) cout << 'l'; if (it->rightnode != NULL) cout << 'r'; if (it->parentnode == NULL) cout << 'H'; cout << " "; } cout << endl; } int main() { CRBTree<int> rbtree; for (int i=0; i<61; i++) { rbtree.Insert(i); printtree(rbtree); } int arrint[] = {1, 7, 5, 20, 4, 6, 9, 10, 17, 3, 2, 15, 60, 55}; for (unsigned int i=sizeof(arrint)/sizeof(arrint[0]); i>0; i--) { rbtree.Erase(arrint[i-1]); printtree(rbtree); } rbtree.clear(); return 0; }