c++红黑树的插入
#includeusing namespace std; enum Color{ RED, BLACK, }; template struct RBTreeNode { K _key; V _value; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Color _color; RBTreeNode(const K& key, const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _color(RED) {} }; template class RBTree { public: typedef RBTreeNode Node; RBTree() :_root(NULL) {} bool Insert(const K& key, const V& value) { if (_root == NULL) { _root = new Node(key,value); _root->_color = BLACK; return true; } Node* cur = _root, *prev = NULL; while (cur) { if (cur->_key < key) { prev = cur; if (cur->_right){ cur = cur->_right; } else { cur->_right = new Node(key, value); cur = cur->_right; cur->_parent = prev; break; } } else if (cur->_key>key) { prev = cur; if (cur->_left){ cur = cur->_left; } else { cur->_left = new Node(key, value); cur = cur->_left; cur->_parent = prev; break; } } else return false; } Node* gf = prev->_parent; while (gf) { if (prev->_color == BLACK) break; Node* uc = NULL; if (prev == gf->_left) uc = gf->_right; else uc = gf->_left; if (uc == NULL||uc->_color==BLACK) { //单旋 if (prev == gf->_left&&cur == prev->_left){//右旋 RotateR(prev, gf); prev->_color = BLACK; gf->_color = RED; } else if (prev == gf->_right&&cur == prev->_right){//左旋 RotateL(prev, gf); prev->_color = BLACK; gf->_color = RED; } //双旋 else if (prev == gf->_right&&cur == prev->_left)//右左旋 { RotateR(cur,prev); RotateL(prev,gf); prev->_color = BLACK; gf->_color = RED; } else//左右旋 { RotateL(cur, prev); RotateR(prev, gf); prev->_color = BLACK; gf->_color = RED; } } else { prev->_color = BLACK; uc->_color = BLACK; if (gf == _root) return true; gf->_color = RED; cur = gf; prev = cur->_parent; gf = prev->_parent; } } return true; } void RotateR(Node* subL,Node* parent) { Node* ppNode = parent->_parent; Node* subLR = subL->_right; subL->_right = parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; if (ppNode){ subL->_parent = ppNode; if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } else _root = subL; } void RotateL(Node* subR, Node* parent) { Node* ppNode = parent->_parent; Node* subRL = subR->_left; subR->_left = parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (ppNode){ subR->_parent = ppNode; if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; } else _root = subR; } bool Remove(const K& key) { } bool IsBalance()//是否平衡 { if (_root == NULL) return true; int num = 0; Node* tmp = _root; while (tmp) { if (tmp->_color == BLACK) num++; tmp = tmp->_left; } return _IsBalance(_root,num); } private: Node* _root; bool _IsBalance(Node* root, int num) { if (root == NULL) return true; if (root->_color == BLACK) num--; if (root->_color == RED){ if (root->_left&&root->_left->_color == RED || root->_right&&root->_right->_color == RED) { cout << "color not balance! key:" << root->_key << endl; return false; } } if (root->_left == NULL&&root->_right == NULL) { if (num == 0) return true; else { cout << "num not balance! key:" << root->_key << endl; return false; } } return _IsBalance(root->_left, num) && _IsBalance(root->_right, num); } };
分享文章:c++红黑树的插入
链接URL:http://scyanting.com/article/jpehdj.html