一.红黑树的概念与性质

1.概念

红黑树是二叉搜索数的一种, 相比于AVL树(二叉平衡搜索树)红黑树通过减少旋转的次数来进一步优化了查找效率, 在每个节点上增加一个存储位表示节点的颜色, Red or Black, 通过对任何一条从根到叶子的路径上各个节点着色方式的限制, 红黑树确保没有一条路径会比其他路经长超出两倍, 故是接近平衡的, 红黑树通过控制五条规则来确保它的近平衡性, 从而既不频繁旋转, 又保证效率在logN级别

2.性质

1).每个节点不是红色就是黑色

2).根节点总是黑色

3).每条路径的NIL节点都是黑色的

4).每条路径的黑色节点数量必须相同

5).每条路径不能用两个连续的红色节点

二.红黑树insert模拟实现

1.为何插入的新节点都是红色的

插入新节点为红色, 然后再根据规则向上调整, 只调整当前分支即可, 如果插入新节点为黑色, 根据红黑树的要求每条路径黑色节点都相同, 则需要调整所有路径, 故为了便于实现, 默认插入的新节点都为红色

2.红黑树插入节点的三种情况

父亲为黑不需要处理

情况一: 父节点为红, 叔叔节点为红

情况二: 父节点为红, 叔叔节点为空/黑, 新插入节点一边倒, 单旋

情况三: 父节点为红, 叔叔节点为空/黑, 新插入节点在中间, 双旋

3.代码

#define _CRT_SECURE_NO_WARNINGS 1enum Color
{RED,BLACK
};template
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;Color _col;pair _kv;//构造RBTreeNode(const pair& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//默认添加的新节点为红色,_kv(kv){}
};template
class RBTree
{
public:typedef RBTreeNode Node;bool insert(const pair& val){if (root == nullptr){//如果此时为空树root = new Node(val);//将根节点修正为黑色root->_col = BLACK;return true;}Node* cur = root;Node* parent = nullptr;//cur的父节点while (cur){if (cur->_kv.first > val.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < val.first){parent = cur;cur = cur->_right;}else//(cur->_kv.first == val.first){//如果插入的节点是重复值, 则插入失败return false;}}cur = new Node(val);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else if (parent->_kv.first < cur->_kv.first){parent->_right = cur;}cur->_parent = parent;//以上为插入节点//-------------------------------------------------------//以下为调整为红黑树//因为默认插入的节点为红色,所以如果出现了两个连续为红的节点就需要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle = nullptr;//确定叔叔节点的位置if (grandfather->_left == parent){uncle = grandfather->_right;}else//grandfather->_right == parent{uncle = grandfather->_left;}//将分为三种情况//1.父节点为红,叔叔节点存在且为红(变色 + 向上迭代)//2/3.父节点为红,叔叔节点不存在或者存在且为黑(旋转 + 变色)if (uncle && uncle->_col == RED)//情况一{//父变黑,叔叔变黑,祖父变红->向上迭代parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况二/三{//情况二//     g//   p   u// cif (uncle == grandfather->_right && cur == parent->_left){//右单旋RotateR(grandfather);//parent->_col = BLACK;grandfather->_col = RED;break;}//     g//   u   p//         c else if (uncle == grandfather->_left && cur == parent->_right){//左单旋RotateL(grandfather);//parent->_col = BLACK;grandfather->_col = RED;break;}//情况三//     g//   u   p//     celse if (uncle == grandfather->_left && cur == parent->_left){//左双旋RotateRL(grandfather);//grandfather->_col = RED;cur->_col = BLACK;break;}//     g//   p   u//     celse if (uncle == grandfather->_right && cur == parent->_right){//右双旋RotateLR(grandfather);//grandfather->_col = RED;cur->_col = BLACK;break;}else{cout << "不存在这种情况" << endl;exit(-1);}}}root->_col = BLACK;return true;}void inorder(){_inorder(root);}//检查是否为红黑树bool isRBTree(){if (root->_col == RED){cout << "出错: 根节点为红" << endl;return false;}//判断是否有连续红节点,且每条路径的黑节点是否相等int benchmark = 0;//算出最左路径的黑节点个数Node* cur = root;while (cur){if (cur->_col == BLACK){++benchmark;}cur = cur->_left;}return _isRBTree(root, 0, benchmark);}private://四种旋转void RotateL(Node* prev){Node* subR = prev->_right;Node* subRL = subR->_left;Node* ppNode = prev->_parent;prev->_right = subRL;if (subRL){subRL->_parent = prev;}subR->_left = prev;prev->_parent = subR;if (root == prev){root = subR;}else{if (ppNode->_left == prev){ppNode->_left = subR;}else{ppNode->_right = subR;}}subR->_parent = ppNode;}void RotateR(Node* prev){Node* subL = prev->_left;Node* subLR = subL->_right;Node* ppNode = prev->_parent;subL->_right = prev;prev->_parent = subL;prev->_left = subLR;if (subLR){subLR->_parent = prev;}if (root == prev){root = subL;}else{if (ppNode->_left == prev){ppNode->_left = subL;}else{ppNode->_right = subL;}}subL->_parent = ppNode;}void RotateRL(Node* prev){//先右旋, 再左旋RotateR(prev->_right);RotateL(prev);}void RotateLR(Node* prev){//先左旋, 再右旋RotateL(prev->_left);RotateR(prev);}void _inorder(Node* root){if (root){_inorder(root->_left);cout << root->_kv.first << "--" << root->_kv.second << endl;_inorder(root->_right);}}//检查是否为红黑树bool _isRBTree(Node* root, int blackNum, int benchmark){if (root == nullptr)//走到空节点{if (benchmark == blackNum){//for debug//cout << blackNum << endl;return true;}else{//for debug//cout << blackNum << endl;cout << "不是所有路径的黑色节点个数都相同" << endl;return false;}}if (root->_col == BLACK){++blackNum;}//判断是否有连续的红节点if (root->_col == RED && root->_parent->_col == RED){cout << "出现了连续的红色节点" << endl;return false;}return _isRBTree(root->_left, blackNum, benchmark)&& _isRBTree(root->_right, blackNum, benchmark);}Node* root = nullptr;
};