目录
- 红黑树的概念
- 红黑树的结构
- 红黑树的插入
- 红黑树的验证
红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树的结构
enum Colour
{
RED,
BLACK
};
template<class k,class v>
struct RBTreeNode
{
public:
RBTreeNode(const pair<k,v>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_cor(RED)
,_kv(kv)
{}
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair<k, v> _kv;
Colour _cor;
};
template<class k, class v>
class RBTree
{
typedef RBTreeNode<k, v> Node;
public:
bool Insert(const pair<k, v>& kv);
private:
Node* _root = nullptr;
};
红黑树的插入
AVL树的学习
最简单的情况：cur为红，p为红，g为黑，u存在且为红
这种情况不需要考虑cur是在p的左还是右，只需要简单的变色，然后继续向上调整
然后要考虑的是u不存在或u为黑时的情况
这时候就需要考虑cur在p的左还是右
bool Insert(const pair<k, v>& kv)
{
if (_root == nullptr)
{
Node* newnode = new Node(kv);
_root = newnode;
_root->_cor = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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;
}
}
Node* newnode = new Node(kv);
newnode->_cor = RED;
if (parent->_kv.first > newnode->_kv.first)
{
parent->_left = newnode;
newnode->_parent = parent;
}
else if (parent->_kv.first < newnode->_kv.first)
{
parent->_right = newnode;
newnode->_parent = parent;
}
else
{
return false;
}
cur = newnode;
parent = cur->_parent;
//插入节点的父亲是黑色，直接结束插入
//cur是红色的
//parent是红色则调整
//grand肯定存在且是黑色
while (parent && parent->_cor == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
// g
// p u(?)
//c
Node* uncle = grandparent->_right;
//uncle存在，且为红色，c的位置不用在意
// g
// p u
//c
if (uncle && uncle->_cor == RED)
{
//p u改成黑色，g改成红色，p变为cur，g变为parent，继续向上检查
parent->_cor = uncle->_cor = BLACK;
grandparent->_cor = RED;
cur = grandparent;
parent = grandparent->_parent;
}
//如果uncle不存在或者为黑色，c的位置需要注意
// g
// p u
//c1 c2
else
{
if (cur == parent->_left)
{
//左左，对g右单旋，p变为新的子树的头
RotateR(grandparent);
//变色，p变黑，g变红
parent->_cor = BLACK;
grandparent->_cor = RED;
}
else if (cur == parent->_right)
{
//左右，先对p左单旋，再对g右单旋
RotateL(parent);
RotateR(grandparent);
//变色，cur变为新的头，黑色，g变红
cur->_cor = BLACK;
grandparent->_cor = RED;
}
else
{
assert(false);
}
//新的头已经是黑色，没必要再向上检查
break;
}
}
else if (parent == grandparent->_right)
{
// g
// u? p
// c
Node* uncle = grandparent->_left;
//uncle存在，且为红色，c的位置不用在意
// g
// u p
// c
if (uncle && uncle->_cor == RED)
{
//p u改成黑色，g改成红色，p变为cur，g变为parent，继续向上检查
parent->_cor = uncle->_cor = BLACK;
grandparent->_cor = RED;
cur = grandparent;
parent = grandparent->_parent;
}
//如果uncle不存在或者为黑色，c的位置需要注意
// g
// u p
// c1 c2
else
{
if (cur == parent->_right)
{
//右右，对g左单旋，p变为新的子树的头
RotateL(grandparent);
//变色，p变黑，g变红
parent->_cor = BLACK;
grandparent->_cor = RED;
}
else if (cur == parent->_left)
{
//右左，先对p右单旋，再对g左单旋
RotateR(parent);
RotateL(grandparent);
//变色，cur变为新的头，黑色，g变红
cur->_cor = BLACK;
grandparent->_cor = RED;
}
else
{
assert(false);
}
//新的头已经是黑色，没必要再向上检查
break;
}
}
else
{
assert(false);
}
}
_root->_cor = BLACK;
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//subR变成新的子树的头，parent链接到subR左边，并把subRL链接到自己右边
subR->_left = parent;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentParent;
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else if (parentParent->_right == parent)
{
parentParent->_right = subR;
}
else
{
assert(false);
}
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//subL变成新的子树的头，parent链接到subL右边，并把subLR链接到自己左边
subL->_right = parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentParent;
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else if (parentParent->_right == parent)
{
parentParent->_right = subL;
}
else
{
assert(false);
}
}
}
红黑树的验证
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
- 检测其是否满足红黑树的性质
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
bool Check(Node* root,int sum,int standval)
{
if (root == nullptr)
{
if (sum != standval)
{
cout << "路径上的黑色节点个数不相同" << endl;
return false;
}
return true;
}
//如果红色孩子的父亲是红色，说明违反了规则
if (root->_cor == RED && root->_parent->_cor == RED)
{
cout << "出现重复的红色节点" << endl;
return false;
}
//如果当前节点是黑色，当前路径黑节点个数加一
if (root->_cor == BLACK)
sum++;
return Check(root->_left,sum, standval)
&& Check(root->_right,sum, standval);
}
bool IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_cor == RED)
return false;
//判断一个红色节点的孩子是不是都是黑色
//判断每个节点的黑色节点的个数,用标准值去比较
int standval = 0;
Node* cur = _root;
while (cur)
{
if (cur->_cor == BLACK)
{
standval++;
}
cur = cur->_left;
}
int sum = 0;
return Check(_root,sum,standval);
}
