红黑树
是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
性质
- 每个节点，非黑即红。
- 根节点必须为黑。
- 如果一个结点是红色的，它的两个子节点一定是黑色的。
- 对于每一条路径而言，黑色节点的个数都是相同的。
红黑树节点
enum Color
{
RED,
BLACK
};
//红黑树节点结构体
template<class K,class V>
class RBTreeNode
{
public:
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Color _col;
RVTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
{}
};红黑树的插入实现
template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K,V>& kv);
/...
private:
Node* _root=nullptr;
};问题：
插入节点时，红黑树需要调整颜色/或者旋转，那我插入的新节点应该是默认红色还是黑色呢？
?默认红色，可能违反规则3。默认黑色，一定违反规则4。而且想要调节规则四更为麻烦，所以默认插入的新节点都是红色。
情况一：单纯变色
1.p为红，g为黑，u存在且为红 ，cur是新插入的，且为红
2.p为红，g为黑，u存在且为红 ，cur是变红的。
此时 c? d e 可以为以下四种
?处理方案：p和u变黑，g变红。再将g赋给cur，继续向上调整
bool Insert(const pair<K,V>&kv)
{
//查找新节点位置与之前二叉搜索树和AVL树相似，具体代码会在最后
//....
//省略了找了位置 并创建了cur节点 链接到了parent
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);
// 关键看叔叔
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情况一 : uncle存在且为红，变色+继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
// 继续往上处理
cur = grandfater;
parent = cur->_parent;
}
else
{
//其他情况
}
}
}
_root->_col=BLACK;
return true;
}情况二：单选+变色
cur为红，p为红，p为黑，u不存在或存在为黑。抽象图如下
1.u不存在。因为保证红黑树的相关规则，abcde必须全为空，此时cur是新插入的且为红
?
?2.u存在且为黑，此时cur是变红的
2的A情况： cur在较高左子树的左边
?
?未插入时 （左边）c是四种情况之一，d、e要么红要么空
插入后（右边）a、b、c一定有黑
处理：单选+变色
对g进行右单选，p变黑，g变红
?代码
bool Insert(const pair<K,V>&kv)
{
//...
while (parent && parent->_col == RED)
{
//...
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
if (uncle && uncle->_col == RED)
{
//...
}
else
{
// 情况二：右单旋+变色
// g
// p u
// c
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
//情况三 ：双旋+变色
// g
// p u
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
}
}
else
{
//无非是cur跑到右树了 parent==grandfather->_right 思想是一样的
}
}
_root->_col=BLACK;
return true;
}情况三：双旋+变色
cur为红，p为红，p为黑，u不存在或存在为黑。抽象图如下
1.u不存在? 所以a、b、c、d、e均不存在 cur是新增节点且为红
?
2.u存在且为黑? cur是变红的
?
?代码：
bool Insert(const pair<K,V>&kv)
{
//...
while (parent && parent->_col == RED)
{
//...
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
if (uncle && uncle->_col == RED)
{
//...
}
else
{
if (cur == parent->_left)
{
//...
}
else
{
//情况三 ：双旋+变色
// g
// p u
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
}
}
else
{
//无非是cur跑到右树了 parent==grandfather->_right 思想是一样的
}
}
_root->_col=BLACK;
return true;
}红黑树的插入实现完整版
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 = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);
// 关键看叔叔
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情况一 : uncle存在且为红，变色+继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
// 继续往上处理
cur = grandfater;
parent = cur->_parent;
}// 情况二+三：uncle不存在 + 存在且为黑
else
{
// 情况二：右单旋+变色
// g
// p u
// c
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情况三：左右单旋+变色
// g
// p u
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else // (parent == grandfater->_right)
{
Node* uncle = grandfater->_left;
// 情况一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
// 继续往上处理
cur = grandfater;
parent = cur->_parent;
}
else
{
// 情况二：左单旋+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情况三：右左单旋+变色
// g
// u p
// c
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}左旋和右旋 和AVL树的差不多 记得放到私有里
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_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;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
?红黑树的检验方法
template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K,V>& kv)
{ //...
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
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 PrevCheck(_root, 0, benchmark);
}
private:
void RotateL(Node* parent)
{//...}
void RotateR(Node* parent)
{//...}
bool PrevCheck(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)
{
if (blackNum != benchmark)
{
cout << "某条黑色节点的数量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}
};?