1. 红黑树概念
红黑树 是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是red或black，
通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长处两倍，所以是接近平衡的
2. 红黑树性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
(不能出现连续的红色节点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
(每条路径上都有相同数量的黑色节点)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
(走到NULL才算一条路径)
3. 结构定义
使用枚举来记录红色与黑色，用_col表示当前节点颜色
但是在构造函数中为什么默认是红色呢？为什么不能是黑色呢？
关于默认节点为红/黑色的讨论
若在红框中插入黑色节点则违反规则4 即每条路径上都有相同数量的黑色节点，还需要再次将不同路径上都添加黑色节点，影响太大
若在红框中插入红色节点，则有可能违反规则3(存在两个连续的红色节点)
当前情况违反规则3
若插入红色节点后，父节点为黑色，则不违反规则3
所以默认节点为红色更利于去解决问题
4. insert
grandfather节点省略为g ，uncle节点省略为u ，parent节点省略为p，cur节点省略为c
情况1—— uncle节点存在且为红色(g p c左斜形成一条直线)
当插入红色节点后，与父节点形成连续的红色节点
把parent节点变成黑色，uncle节点置为黑色，并将grandfather节点置为红色
若grandfather节点的父节点为黑色，则不需要继续处理
若grandfather节点的父节点为红色，把当前的grandfather节点作为新增节点cur，继续向上调整
情况2——uncle节点不存在/存在且为黑色(g p c 左斜形成直线 右单旋)
uncle节点不存在
当uncle节点不存在时，则cur作为新增节点，
因为红黑树也是一种二叉搜索树，因为左边高，所以进行右单旋
uncle节点存在并且为黑色
首先进行变色，将新增节点的上面两个节点置为黑色，再将cur节点置为红色
同时需要进行右旋转
将c作为g的左子树，将g作为p的右子树
将g置为红色
将p置为黑色
RotateR/RotateL的实现，与AVL树的类似，只需把原来的代码的平衡因子去掉即可
不懂查看：AVL树的实现
情况3——uncle节点不存在/存在且为黑色(g p c 形成左折线 双旋)
因为 grandfather(g) parent( p) cur( c) 节点为一条折线，所以为双旋
uncle节点不存在
作为这样的折线存在，所以要进行双旋，先对p进行右单旋，在对旋转后的根进行左单旋
uncle节点存在并且为黑色
首先进行变色，将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色
在进行左单旋，将cur的左子树节点 作为p的右子树，将p作为cur的左子树
进行右单旋，将cur的右子树节点作为g的左子树，将g作为cur的右子树
最终cur变为黑色，g变为红色
情况1—— uncle节点存在且为红色(g p c右斜形成一条直线)
当插入红色节点后，与父节点形成连续的红色节点
把parent节点变成黑色，uncle节点置为黑色，并将grandfather节点置为红色
若grandfather节点的父节点为红色，把当前的grandfather节点作为新增节点cur，继续处理
与上述左斜形成直线的写法相同
情况2——uncle节点不存在/存在且为黑色(g p c 右斜形成直线 左单旋)
这里以节点不存在举例
此时的uncle节点处于NULL
将parent节点置为黑色，将grandfather节点置为红色
并进行旋转，将1作为6的左子树，将6作为8的左子树
相当于进行左单旋
情况3——uncle节点不存在/存在且为黑色(g p c 形成右折线 双旋)
首先进行变色，将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色
在进行右单旋，将cur的右子树节点 作为p的左子树，将p作为cur的右子树
进行左单旋，将cur的左子树节点作为g的右子树，将g作为cur的左子树
最终cur变为黑色，g变为红色
5.判断是否为红黑树
规则中要求根节点为黑色，所以当根为红色时就返回false
连续的红色节点
若当前节点为红时，检查儿子是否为红，但是儿子节点有可能为空
所以采用当前节点为红时，若父节点也为红，则返回false
使用blacknum用于记录每条路径的黑色节点个数
blacknum作为一个形参传值调用，下一层的++不会影响上一层
如果当前节点的颜色为黑色，则blacknum++
6. 整体代码
#pragma once #include<iostream> #include<cassert> using namespace std; enum colour { RED,//红色 默认为0 BLACK,//黑色 默认为1 }; 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;//用于记录cur的前一个节点 Node* cur = _root; while (cur) { //若插入的值比当前树的值小 插入左边 if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } //若插入的值比当前树的值大 插入右边 else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { //若插入的值，在树中有相同的值 ，则插入失败 return false; } } cur = new Node(kv); //再次判断parent当前节点值与插入值大小 if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } //cur的上一个节点即为 刚才的记录cur前一个节点的parent cur->_parent = parent; //当父节点不为NULL并且父节点为红色 while (parent != nullptr && parent->_col == RED) { Node* grandfather = parent->_parent;//爷爷节点 //若父节点为爷爷节点的左子树，则unlce为爷爷节点的右子树 if (grandfather->_left == parent) { Node* uncle = grandfather->_right; // g // p u // c //情况1:u存在并且为红，直接变色即可，并继续往上处理 if (uncle && uncle->_col == RED) //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色 { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //继续往上调整 cur=grandfather; parent = cur->_parent; } //情况2+3:u不存在或者u存在且为黑，旋转+变色 else { //情况2 //g p c 作为一条直线 所以为单旋 // g // p u //c if (cur == parent->_left) { //右旋转 RotateR(grandfather); //最终p作为最终的根 为黑 g为红 parent->_col = BLACK; grandfather->_col = RED; } //情况3 //g p c 作为一条折线 所以为双旋 // g // p u // c else { //左单旋 RotateL(parent); //右单旋 RotateR(grandfather); //最终cur作为最终的根 为黑 g为红 cur->_col = BLACK; grandfather->_col = RED; //父节点继续保持红色 parent->_col = RED; } break; } } else//grandfather->_right == parent 若父节点为爷爷节点的右子树，则unlce为爷爷节点的左子树 { // g // u p // c Node* uncle = grandfather->_left; //情况1:u存在并且为红，直接变色即可，并继续往上处理 if (uncle && uncle->_col == RED) //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色 { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //继续往上调整 cur = grandfather; parent = cur->_parent; } //情况2+3:u不存在或者u存在且为黑，旋转+变色 else { //情况2 //g p c 作为一条直线 所以为单旋 // g // u p // c if (cur == parent->_right) { //左旋转 RotateL(grandfather); //最终p作为最终的根 为黑 g为红 parent->_col = BLACK; grandfather->_col = RED; } //情况3 //g p c 作为一条折线 所以为双旋 // g // u p // c else { //右单旋 RotateR(parent); //左单旋 RotateL(grandfather); //最终cur作为最终的根 为黑 g为红 cur->_col = BLACK; grandfather->_col = RED; } break; } } } //为了避免grandfather节点正好为根时，会被更新成红色的情况 _root->_col = BLACK; return true; } void inorder()//中序遍历 { _inorder(_root); cout << endl; } //判断一颗二叉树是否为红黑树 bool isbalance() { //检查根是否为黑 if (_root && _root->_col == RED) { cout << "根节点颜色是红色" << endl; return false; } //连续的红色节点 return _check(_root,0); } private: bool _check(Node* root,int blacknum) { if (root == nullptr) { //为空时，blacknum代表一条路径的黑色节点个数 cout << blacknum << " "; return true; } //blacknum代表黑色节点的个数 if (root->_col == BLACK) { blacknum++; } //若当前节点为红 父节点也为红 if (root->_col == RED &&root->_parent &&root->_parent->_col==RED) { cout << "存在连续的红色节点" << endl; return false; } //遍历整棵树 return _check(root->_left,blacknum) && _check(root->_right,blacknum); } void _inorder(Node* root) { if (root == nullptr) { return; } _inorder(root->_left); cout << root->_kv.first << " "; _inorder(root->_right); } void RotateL(Node* parent)//左单旋 { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL != nullptr) { subRL->_parent = parent; } Node* ppnode = parent->_parent;//记录parent的前一个节点 subR->_left = parent; parent->_parent = subR; if (ppnode == nullptr)//说明parent是根即代表整棵树 { _root = subR;//subR作为新的根 _root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr } else//说明旋转的是一部分，所以要跟ppnode相连接 { if (ppnode->_left == parent)//若连接在左子树上 { ppnode->_left = subR; } else//若连接在右子树上 { ppnode->_right = subR; } subR->_parent = ppnode;//将subR父节点置为ppnode } } void RotateR(Node* parent)//右单旋 { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR != nullptr) { subLR->_parent = parent; } Node* ppnode = parent->_parent;//记录parent的父节点 subL->_right = parent; parent->_parent = subL; if (ppnode == nullptr)//若旋转整棵树 { _root = subL; _root->_parent = nullptr; } else//若旋转整棵树的部分子树 { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode;//使subL的父节点为ppnode } } private: Node* _root = nullptr; }; void test_RBTree1() { int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15}; //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 }; RBTree<int, int>v1; for (auto e : a) { v1.insert(make_pair(e, e)); } v1.inorder(); cout << v1.isbalance() << endl; }
