红黑树特性总结
目录
认识红黑树：
红黑树的平衡调节：
情况一：
情况二：
情况三：
代码：
认识红黑树：
红黑树和AVL树一样，也是一种平衡二叉树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确没有一条路径会比其他路径长出俩倍，因而是接近平衡的。虽然它的平衡性没有AVL树那么好，但实际上效率几乎一样，而且它比AVL树更好控制。对于红黑树的规则如下：
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
只需满足以上特性，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍。 下图，就是红黑树：
红黑树的平衡调节：
认识了红黑树，它到底是如何进行平衡调节的呢？先列举它需要调节平衡的时候，大致可分为两类，先约定，cur为当前节点，p为父节点，g为祖先节点，u为叔叔节点。
情况一：
叔叔存在且为红色：
这种时候p节点已经不满足特性2了，我们需要调整，方法：p，u改为黑，g改为红，注意如果g是根节点就再改为黑：
只需简单改色，就可让这颗树重新满足红黑树特性。
注意，到这里还没有结束，因为这颗树可能是别人的子树，改色后，可能出现下图的情况 ：
祖先节点的父节点，可能是红的，这样最后就两个红色在一起了，我们需要将cur=g，p=g->parent，继续向上更新，直到父节点为黑色或者空（父节点为空时就是根节点）
情况二：
cur为红，p为红，g为黑，u不存在/u存在且为黑：
说明:u的情况有两种 1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点 则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个 数相同。 2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的 现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由 黑色改成红色。
这两种情况都可以用一种方法处理： p变黑，g变红，然后以g为旋转点，进行右单旋（旋转相关的知识可以看我上一篇博客）
情况三：
情况三和情况二只有一个区别就是，cur为情况二图中p的右子树，其余条件完全相同：
调整方法： 先以p为旋转点进行左旋后，可以发现已经和情况二一样了，不过这时的p和cur和情况二中的p和cur是反过来的（旋转造成的），我们再交换p和cur就和情况二一样了（不交换也可以变色时让cur变色），然后再按情况二的调整方法，先p变黑，g变红，以g为旋转点右旋。
特别注意：上图列出的三种情况，都是叔叔节点在祖先节点右边的情况，实际还需考虑叔叔节点在祖先节点左边的情况，两种情况方法原理完全相同，只需颠倒一下，左旋变右旋，右旋变左旋。
代码：
#pragma once
#include<string>
enum colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTNode
{
AVLNode<K, V>* _left;//左子树
AVLNode<K, V>* _right;//右子树
AVLNode<K, V>* _parent;//父节点
pair<K, V> _kv;
colour _clo;
RBNode(const pair<K, V>& kv)//构造函数
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
,_clo(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBNode<K, V> node;
public:
bool insert(const pair<K,V>& kv)
{
if (_root == nullptr)//若原来树为空
{
_root = new node(kv);
_root->_col = RED;
return true;
}
node* cur = _root;
node* parent = nullptr;
while (cur)//开始找插入位置
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = parent->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = parent->_right;
}
else
{
return false;
}
}
cur = new node(kv);
cur->col = RED;
if (kv.first > parent->_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->_col == RED)//若叔叔为红，p,u改黑，g改红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
if (grandfather == _root)//g为根，再次变黑
{
grandfather->_col = BLACK;
}
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else//若叔叔不存在或者为黑
{
if (cur == parent->_left)
{
// g
// p u
// c
//g变红，p变黑，右旋
grandfather->_col = RED;
parent->_col = BLACK;
RotateR(grandfather);
}
else
{
// g
// p u
// c
//g变红，c变黑，先以p左旋，再以g右旋
grandfather->_col = RED;
cur->_col = BLACK;
RotateL(parent);
RotateR(grandfather);
}
break;//这种情况无需再向上更新
}
}
else//父在爷爷的右
{
node* uncle = grandfather->left;
if (uncle->_col == RED)//若叔叔为红，p,u改黑，g改红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
if (grandfather == _root)//g为根，再次变黑
{
grandfather->_col = BLACK;
}
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else//若叔叔不存在或者为黑
{
if (cur == parent->_left)
{
// g
// u p
// c
//g变红，c变黑，先以p右旋，再以g左旋
grandfather->_col = RED;
cur->_col = BLACK;
RotateR(parent);
RotateL(grandfather);
}
else
{
// g
// u p
// c
//g变红，p变黑，左旋
grandfather->_col = RED;
parent->_col = BLACK;
RotateL(grandfather);
}
break;//这种情况无需再向上更新
}
}
}
}
void RotateR(node* parent)
{
//调节节点
node* subL = parent->_left;
node* subLR = subL->_right;
node* ppnode = parent->_parent;
parent->_left = subLR;
if (subLR)//防止为空
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
//调节父节点的指向
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
node* ppnode = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
parent->_parent = subR;
subR->_right = parent;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
private:
node* _root;
};