一.红黑树概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
二.红黑树性质
-
每个结点不是红色就是黑色
-
根节点是黑色的
-
如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点）
-
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径都存在相同数量的黑色节点）
-
每个叶子结点都是黑色的(此处的叶子结点指的是空结点NULL)
如何理解红黑树最长路径不超过最短路径的二倍呢？？？
- 从性质能够看出，红黑树每一条路径上，都有相同数量的黑色节点。
- 红黑树每条路径上可以存在连续的黑色节点，但不能存在连续的红色节点。
- 所以最短路径即为全是黑色节点的路径。
- 最长路径则为一黑一红相间的路径。
三.红黑树实现
1.基本框架
红黑树与AVL树相比，多了节点颜色这一信息，为了实现这一信息，我们使用枚举：
enum Colour
{
RED,
BLACK
};
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:
private:
Node* _root = nullptr;
size_t _size = 0;
};同时我们多创建一个_size成员变量，用于记录节点数量。
2.插入
红黑树插入的基本步骤与二叉搜索树和AVL树一样，都是按照左子节点比根节点小，右子节点比根节点大的规则，唯一不同的是，红黑树的插入要考虑其性质。其中最值得注意的性质为：
- 不存在连续的红节点
- 每条路径上的黑节点数相等
其中能够看出，第二条才是最关键的，因此我们每次新插入节点时，必须插入红节点。
此时我们会面临两种情况：
- 父节点为黑色，插入即结束，无需调整。
- 父节点为红色，不满足上述性质1，需要调整。
下面我们来看特殊情况：
父亲为红节点，那么只有将父节点变为黑色节点，才能够满足性质。
但是如果父亲变为黑节点，就说明该路径上同样多出一个黑节点，而唯一的处理手段，就是让父亲的父亲，也就是爷爷节点，变为红色节点。
此时又存在问题，那就是关于父亲的兄弟节点，也就是叔叔节点，那么叔叔节点存在三种情况：
- 叔叔节点同样为红色。
- 叔叔节点不存在。
- 叔叔节点为黑色。
如果叔叔节点为红色，为了满足各路径黑节点数量相同，叔叔节点则需要和父节点一起变为黑色。
如果叔叔节点不存在，为了满足性质，需要将该子树从爷爷节点的位置进行旋转。
如果叔叔节点为黑色，而父节点为红色，如果还要满足性质，说明子节点原本应为黑色，是因为经过了上述的调整而作为爷爷节点变成了红色。此时我们仍需从爷爷节点的位置进行旋转。
分析完上述完整情况之后，还有关于新插入节点的两种情况：
- 父节点为爷爷节点的左子节点，同时新增节点也为父节点的左子节点，为一条斜线。
- 父节点为爷爷节点的左子节点，但是新增节点也为父节点的有子节点，为一条折线。
斜线情况下，我们在需要旋转时只需单旋即可；
而当为折线时，就需要进行双旋，先变为斜线，在进行调整。
同时父节点也需要考虑是爷爷节点的左节点还是右节点两种情况，彼此的规则相反。
按照上边的步骤，我们能够得出代码情况：
//插入
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 (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//parent是黑色就结束
while (parent && parent->_col == RED)
{
Node* Grandfather = parent->_parent;
if (parent == Grandfather->_left)
{
Node* uncle = Grandfather->_right;
if (uncle && uncle->_col == RED)//叔叔存在且为红，直接变色
{
parent->_col = BLACK;
uncle->_col = BLACK;
Grandfather->_col = RED;
//继续往上处理
cur = Grandfather;
parent = Grandfather->_parent;
}
else//叔叔不存在或叔叔存在但为黑
{
if (cur == parent->_left)//左边直接右旋
{
RotateR(Grandfather);
parent->_col = BLACK;
Grandfather->_col = RED;
}
else//右边则左右双旋
{
RotateL(parent);
RotateR(Grandfather);
cur->_col = BLACK;
Grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = Grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
Grandfather->_col = RED;
cur = Grandfather;
parent = Grandfather->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(Grandfather);
Grandfather->_col = RED;
parent->_col = BLACK;
}
else
{
RotateR(parent);
RotateL(Grandfather);
cur->_col = BLACK;
Grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}需要考虑的情况确实很多，但如果自己画图认真分析，理解起来还是易如反掌的。
3.判断平衡
判断红黑树的平衡，我们自然要从其性质入手：
- 首先就是判断根节点是否为黑色。
- 其次容易判断的是是否有两个相邻的红色节点，注意这里我们不去判断一个节点与其子节点，反而去判断一个节点与其父节点。因为如果判断子节点，则可能需要判断两次，而父节点则只需判断一次。
- 最后就是判断所有路径上的黑节点数量是否相同。
其中前两种都比较容易想到代码方式，最重要的是如何比较黑节点的数量。
我们可以通过增加参数的方式。来记录到达每个节点位置时，该路径上出现过的黑节点的数量。而如何进行比较，因为每条路径上黑节点的数量都必须相同，所以我们直接记录一下最左边的一条路径上黑节点的数量，然后求出一条路径上的黑节点数之后，就进行比较即可。
//判断平衡
bool IsBalance()
{
if (_root->_col == RED)
return false;
int refnum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
refnum++;
cur = cur->_left;
}
return Check(_root, 0, refnum);
}
bool Check(Node* root, int BlackNum,const int refnum)
{
if (root == nullptr)
{
if (refnum != BlackNum)
{
cout << "存在黑色节点个数不相等" << endl;
return false;
}
cout << BlackNum << endl;
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "->存在连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
BlackNum++;
return Check(root->_left, BlackNum,refnum)
&& Check(root->_right, BlackNum,refnum);
}四.完整代码
enum Colour
{
RED,
BLACK
};
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;
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 (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//parent是黑色就结束
while (parent && parent->_col == RED)
{
Node* Grandfather = parent->_parent;
if (parent == Grandfather->_left)
{
Node* uncle = Grandfather->_right;
if (uncle && uncle->_col == RED)//叔叔存在且为红，直接变色
{
parent->_col = BLACK;
uncle->_col = BLACK;
Grandfather->_col = RED;
//继续往上处理
cur = Grandfather;
parent = Grandfather->_parent;
}
else//叔叔不存在或叔叔存在但为黑
{
if (cur == parent->_left)//左边直接右旋
{
RotateR(Grandfather);
parent->_col = BLACK;
Grandfather->_col = RED;
}
else//右边则左右双旋
{
RotateL(parent);
RotateR(Grandfather);
cur->_col = BLACK;
Grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = Grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
Grandfather->_col = RED;
cur = Grandfather;
parent = Grandfather->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(Grandfather);
Grandfather->_col = RED;
parent->_col = BLACK;
}
else
{
RotateR(parent);
RotateL(Grandfather);
cur->_col = BLACK;
Grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
//右单旋
void RotateR(Node* parent)
{
//定义左子节点
Node* subL = parent->_left;
//定义左子节点的右子节点
Node* subLR = subL->_right;
//调整
parent->_left = subLR;
//判空
if (subLR)
subLR->_parent = parent;
//调整
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (parent == _root)//判断是否为根
{
_root = subL;
_root->_parent = nullptr;
}
else//不是根节点，调整父节点指向
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
}
//左单旋
void RotateL(Node* parent)
{
//定义右子节点
Node* subR = parent->_right;
//定义右子节点的左子节点
Node* subRL = subR->_left;
//调整
parent->_right = subRL;
//判空
if (subRL)
subRL->_parent = parent;
//调整
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (parent == _root)//判断是否为根
{
_root = subR;
_root->_parent = nullptr;
}
else//不是根节点，调整父节点指向
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
}
//遍历
void InOrder()
{
inOrder(_root);
cout << endl;
}
void inOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
inOrder(root->_left);
cout << root->_kv.first << ':' << root->_kv.second << endl;
inOrder(root->_right);
}
//判断平衡
bool IsBalance()
{
if (_root->_col == RED)
return false;
int refnum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
refnum++;
cur = cur->_left;
}
return Check(_root, 0, refnum);
}
bool Check(Node* root, int BlackNum,const int refnum)
{
if (root == nullptr)
{
if (refnum != BlackNum)
{
cout << "存在黑色节点个数不相等" << endl;
return false;
}
cout << BlackNum << endl;
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "->存在连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
BlackNum++;
return Check(root->_left, BlackNum,refnum)
&& Check(root->_right, BlackNum,refnum);
}
private:
Node* _root = nullptr;
//size_t _size = 0;
};
