本篇博文主旨是介绍红黑树的概念及其性质，并用C++代码进行实现；红黑树的重难点是剖析插入、删除节点的旋转情况；最后再进行了红黑树和AVL树的对比，说明为什么红黑树优于AVL树
红黑树的概念及其性质
除此之外，还有下列特点：
（1）每个节点的颜色为黑色或者红色，并且根节点为黑色
（2）从根节点到每个叶子节点的路径上，黑色节点的数量相同
（3）父亲节点和子节点不能同时为红色，也就是说，没有连续的红节点
（4）从根节点到叶子节点，最长路径不超过最短路径的两倍
红黑树节点的定义
//定义枚举类型变量
//表示节点颜色
enum Color
{
RED,BLACK,};
//红黑树节点的定义
template<typename K,typename V>
struct RBTreeNode
{
//K/V 结构，可以存储一个pair
K _key;
V _value;
//颜色
Color _col;
//节点我们采用三叉链，方便父亲的寻找
RBTreeNode<K,V>* _left;
RBTreeNode<K,V>* _right;
RBTreeNode<K,V>* _parent;
//构造函数
RBTreeNode(const K& key,const V& value)
: _key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_col(RED)
{}
};
红黑树的插入以及旋转情况
这里，我们先定义一下几个节点的名称
parent---插入节点的父亲节点
cur --- 当前插入的节点
grandfather --- parent的父亲节点
uncle --- 叔叔节点，grandfather除parent的另一个子节点
分以下情况讨论
情况1、叔叔存在且为红
当出现如图所示的这种情况时，parent和uncle，cur都为红；
这种情况只需要将parent，uncle的颜色换成黑色，grandfather节点设置为红色的
由于grandfather被设置成红色，那么需要向上调整，因为如果grandfather的父亲如果是红的，修改后就又出现了两个红色节点连续的情况了
情况2、叔叔不存在/叔叔存在，但是为黑色
这里又分两种情况：
a.插入的节点是parent的左孩子，那么直接对grandfather进行右旋，结束调整，因为最上面的节点为黑，不会导致出现两个连续红节点的情况
b.插入的节点是parent的右孩子，先需要对parent进行左旋，转化成a的情况，然后再对grandfather进行右旋，结束调整，因为最上面的节点为黑，不会导致出现两个连续红节点的情况
说明：上面列举的是parent为grandfather的左孩子的情况，反之，当parent是grandfather的右孩子时，也按照上面的方法
左旋和右旋的代码
//和AVL树的旋转逻辑相同，区别仅是不用修改平衡因子 //右旋 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 (ppNode) { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } else { _root = subL; subL->_parent = NULL; } } //左旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if (ppNode) { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } else { _root = subR; subR->_parent = NULL; } }
Insert函数的代码实现
pair<Node*,bool> Insert(const K& key,const V& value)
{
//如果根节点为空，直接插入，并且将节点颜色设置为黑
if (_root == NULL)
{
_root = new Node(key,value);
_root->_col = BLACK;
return make_pair(_root,true);
}
//用cur和parent 判断插入的Key知否存在
//若不存在，用parent来表示要插入的节点的父亲
Node* cur = _root;
Node* parent = NULL;
//进行循环查找
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
//不存在，返回查找到元素的指针，以及插入失败的FALSE
return make_pair(cur,false);
}
}
//进行插入
cur = new Node(key,value);
Node* newNode = cur;
//判断插入的是parent的左孩子还是右孩子
if (key < parent->_key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//进行调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//1.叔叔存在且为红，变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //叔叔不存在/叔叔存在且为黑
{
//2.进行单旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //3.进行双旋
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
//1.叔叔存在且为红，变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //叔叔不存在/叔叔存在且为黑
{
//2.进行单旋
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //3.进行双旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(newNode,true);
}
bool IsBalance()
{
//1.空树，属于红黑树
if (_root == NULL)
return true;
//2.根节点不为黑
if (_root->_col != BLACK)
return false;
//3.统计出一条路径上黑色节点的数量
size_t k = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
k++;
cur = cur->_left;
}
//进行判别条件2和3的判断
return CheckColor(_root) && CheckBlackNum(_root,k,0);
}
如何判断一棵树是否为红黑树
我们可以从下面三个方面判别，需要注意的是，空树也是红黑树
判别1：根节点是否为黑色
判别2：每条路径的黑色节点数量是否相同
判别3：每一个红节点，其父亲节点是否为黑节点
判别1：
bool IsBalance()
{
//1.空树，属于红黑树
if (_root == NULL)
return true;
//2.根节点不为黑
if (_root->_col != BLACK)
return false;
//3.统计出一条路径上黑色节点的数量
size_t k = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
k++;
cur = cur->_left;
}
//进行判别条件2和3的判断
return CheckColor(_root) && CheckBlackNum(_root,0);
}
判别2：
bool CheckColor(Node* root)
{
//1.空树，满足
if (root == NULL)
return true;
//2.判断父亲，是否是连续的红色
if (root->_col == RED && root->_parent->_col == RED)
return false;
return CheckColor(root->_left) && CheckColor(root->_right);
}
判别3：
bool CheckBlackNum(Node* root,const size_t &k,size_t num)
{
//1.空树，满足
if (root == NULL)
return true;
if (root->_col == BLACK)
++num;
//2.叶子节点，判断黑色节点数量
if (root->_left == NULL && root->_right == NULL && num != k)
return false;
return CheckBlackNum(root->_left,num)
&& CheckBlackNum(root->_right,num);
}
红黑树和AVL树的比较
1、红黑树相对AVL树来说，它不追求完全平衡，在他们的增删查改的时间复杂度都为O(lg(N))的情况下，降低了插入节点后的旋转次数；
2、红黑树没有AVL树的平衡因子的判断，实现起来简单了许多
3、而AVL树由于本身追求完全平衡的苛刻性，旋转次数多，旋转因子的判断较为麻烦
红黑树代码实现
下面是实现红黑树的github链接，可以关注一下，一起学习~
https://github.com/haohaosong/DataStruct/blob/master/RBTree.h
