概念与特性
红黑树，是一种自平衡的二叉搜索树，它具有以下特点：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色的。
- 每个叶子节点（NIL节点，空节点）都是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的，也就说，不存在两个连续的红色节点。
- 对于任意节点，从该节点到其后代叶子节点的所有路径上包含相同数目的黑色节点，即保证了红黑树的黑色节点高度相同。
红黑树的定义
enum Colour { RED, BLACK }; template<class K,class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(RED) { } };
红黑树的插入操作
旋转的见：AVL树链接入口
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } //确定插入位置 Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } //确定cur节点和p节点的位置关系 cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; //情况一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //向上处理 cur = grandfather; parent = cur->_parent; } else//情况2 { if (cur == parent->_left) { // g // p u // c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了 } } else { Node* uncle = grandfather->_left; // 情况一：叔叔存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else//情况2 { if (cur == parent->_right) { // g // u p // c RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了 } } } _root->_col = BLACK; return true; }
验证
void TestRBTree1() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; RBTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); } t.InOrder(); cout << t.IsBalance() << endl; }
bool Check(Node* cur, int blackNum, int refBlackNum) { if (cur == nullptr) { //当节点为空时，表示这条路径结束，这时就要对黑色节点进行判断 if (refBlackNum != blackNum) { cout << "与其他路径的黑色节点数不相等" << endl; return false; } return true; } if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_kv.first << "存在连续的红色节点" << endl; return false; } if (cur->_col == BLACK) { blackNum++; } return Check(cur->_left,blackNum,refBlackNum) && Check(cur->_right,blackNum,refBlackNum); } bool IsBalance() { if (_root && _root->_col == RED) return false; //统计一条路径的黑色节点数 int refBlackNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { refBlackNum++; } cur = cur->_left; } return Check(_root,0,refBlackNum); }
红黑树的性能测试
void TestRBTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } //测插入所需时间 size_t begin2 = clock(); RBTree<int, int> t; for (auto a : v) { t.Insert(make_pair(a, a)); } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.IsBalance() << endl; //测高度，数量 cout << "height" << t.Height() << endl; cout << "Size:" << t.Size() << endl; //测查找时间 size_t begin1 = clock(); for (size_t i = 0; i < N; i++) { t.Find((rand() + i)); } size_t end1 = clock(); cout << "Find:" << end1 - begin1 << endl; }
原码
#pragma once enum Colour { RED, BLACK }; template<class K,class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(RED) { } }; template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } //确定插入位置 Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } //确定cur节点和p节点的位置关系 cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; //情况一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //向上处理 cur = grandfather; parent = cur->_parent; } else//情况2 { if (cur == parent->_left) { // g // p u // c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了 } } else { Node* uncle = grandfather->_left; // 情况一：叔叔存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else//情况2 { if (cur == parent->_right) { // g // u p // c RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了 } } } _root->_col = BLACK; return true; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << endl; _InOrder(root->_right); } void InOrder() { _InOrder(_root); } bool Check(Node* cur, int blackNum, int refBlackNum) { if (cur == nullptr) { //当节点为空时，表示这条路径结束，这时就要对黑色节点进行判断 if (refBlackNum != blackNum) { cout << "与其他路径的黑色节点数不相等" << endl; return false; } return true; } if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_kv.first << "存在连续的红色节点" << endl; return false; } if (cur->_col == BLACK) { blackNum++; } return Check(cur->_left,blackNum,refBlackNum) && Check(cur->_right,blackNum,refBlackNum); } bool IsBalance() { if (_root && _root->_col == RED) return false; //统计一条路径的黑色节点数 int refBlackNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { refBlackNum++; } cur = cur->_left; } return Check(_root,0,refBlackNum); } size_t Size() { return _Size(_root); } size_t _Size(Node* root) { if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return NULL; } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); } private: Node* _root = nullptr; }; void TestRBTree1() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; RBTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); } t.InOrder(); cout << t.IsBalance() << endl; } //性能测试 void TestRBTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } //测插入所需时间 size_t begin2 = clock(); RBTree<int, int> t; for (auto a : v) { t.Insert(make_pair(a, a)); } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.IsBalance() << endl; //测高度，数量 cout << "height" << t.Height() << endl; cout << "Size:" << t.Size() << endl; //测查找时间 size_t begin1 = clock(); for (size_t i = 0; i < N; i++) { t.Find((rand() + i)); } size_t end1 = clock(); cout << "Find:" << end1 - begin1 << endl; }
