前言
红黑树是比较重要的一颗树了，map和set的底层就是红黑树，一定要牢牢记住。
一、什么是红黑树
首先：红黑树仍然是一颗搜索二叉树，但他引入了颜色这一概念，每个结点多一个存储位来存储颜色，它通过维护下面五条规则来保证，最长路径不超过最短路径的二倍。
1.每个结点不是黑颜色就是红颜色
2.根节点是黑色
3.如果一个节点是红色，则他存在的孩子节点是黑色，换句话说，任意一条路径不存在连续的红色节点。
4.对于每个节点，到所有NIL节点的路径上，均含有相同数量的黑色节点。
5.每个NIL节点都是黑色的
为什么设计第五条规则？看图：
这五条规则里最重要的就是三和四，插入也要维护三和四。
为什么维护了这五条规则就能达到最长路径不超过最短路径的二倍呢？
最短路径：全是黑色节点
最长路径：一黑一红，又因为黑色节点的数量相同，所以最长的路径最多是最短路径的二倍。
二、模拟
红黑树还是模拟插入过程，还是写成K，V和三叉链结构
节点定义
enum class Color {
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color color;
pair<K, V> _kv;
RBTreeNode(const pair<K,V>& p)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,color(Color::RED)
,_kv(p)
{}
};
这里有两个注意的点：
1.这个枚举是C++新搞出来的，和原来枚举不同的就是不是全局的。
2.节点的默认颜色搞成红色，如果搞成黑色，这一条路径上的黑色节点加一，而其他所有路径上的黑色数目就会相对较少，不好维护，所以违反第三条规则，维护第三条规则，这需要维护这一条和叔叔路径上的。
搜索树的逻辑插入：
bool insert(const pair<K, V>& p)
{
if (_root == nullptr)
{
_root = new Node(p);
_root->color = Color::BLACK;
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first < p.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > p.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(p);
if (parent->_kv.first < p.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//这之前都是搜索树的逻辑
//
调整颜色的逻辑：
while (parent && parent->color == Color::RED)
{
Node* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* uncle = grandf->_right;
//叔叔存在且为红
if (uncle && uncle->color == Color::RED)
{
//判断
uncle->color = parent->color = Color::BLACK;
grandf->color = Color::RED;
//继续判断
cur = grandf;
parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//开旋
if (parent->_left == cur)
{
RotateRight(grandf);
parent->color = Color::BLACK;
grandf->color = Color::RED;
}
else
{
//parent->right 是cur，grandf的左边是parent
RotateLeft(parent);
RotateRight(grandf);
cur->color = Color::BLACK;
grandf->color = Color::RED;
}
}
}
//祖父的右边是父亲
else
{
Node* uncle = grandf->_left;
//uncle不存在 或者uncle为黑
//uncle为红
if (uncle && uncle->color == Color::RED)
{
parent->color = uncle->color = Color::BLACK;
grandf->color = Color::RED;
cur = grandf;
parent = cur->_parent;
}
//uncle为黑或者不存在
else
{
//旋转
// grandf
//uncle parent
//cur
if (cur == parent->_right)
{
RotateLeft(grandf);
parent->color = Color::BLACK;
grandf->color = Color::RED;
}
else
{
RotateRight(parent);
RotateLeft(grandf);
cur->color = Color::BLACK;
grandf->color = Color::RED;
}
}
}
}
_root->color = Color::BLACK;
return true;
}
其实还可以，顺一顺思路：
当父亲存在并且父亲的颜色是红就更新
先判断祖父的左边是父亲还是右边，需要根据这个旋转
然后判断uncle，也就是祖父的另一个孩子，如果uncle为红，和parent一起改颜色，往上更新。
如果为黑或者不存在，要旋转，直线型单旋，折线型双旋，注意控制颜色，旋转完的父亲一定为黑，左右两个孩子都为红。
三、验证是否正确
1.验证是否为二叉搜索树，走一个中序遍历就可以,有序即为二叉搜索树。
2.验证是否红黑树满足条件：
主要是看三和四，三：看有无连续红色节点，利用父亲来判断，
四：看黑色节点的数量，可以先求出一条路径的数量，然后再去递归所有路径进行比较。
bool CheckColor(Node* node,int blacknum,int basic)
{
if (node == nullptr)
{
if (blacknum != basic)
{
cout << "违背了第四条规则" << endl;
return false;
}
return true;
}
if (node->color == Color::BLACK)
{
blacknum++;
}
//检查孩子很麻烦，检查父亲
if (node->color == Color::RED && node->_parent && node->_parent->color == Color::RED)
{
cout << "出现了连续的红色结点" << endl;
return false;
}
return CheckColor(node->_left,blacknum,basic) && CheckColor(node->_right, blacknum, basic);
}
bool _IsBalance(Node* node)
{
if (node == nullptr) return true;
if (node->color != Color::BLACK)
{
//根节点是黑色
return false;//第二条
}
int basic = 0;
Node* cur = node;
while (cur)
{
if (cur->color == Color::BLACK)
{
basic++;
}
cur = cur->_left;
}
return CheckColor(node,0,basic);
}
四、性能
代码测试
int main()
{
RBTree<int, int> rb;
AVLTree<int, int> avl;
srand(time(0));
size_t N = 100000000;
vector<int> v(N);
for (size_t i = 0; i < N; ++i) v[i] = rand() + i;
int begin1 = clock();
for (size_t i = 0; i < N; ++i)
{
rb.insert({ v[i],v[i] });
}
int end1 = clock();
int begin2 = clock();
for (size_t i = 0; i < N; ++i)
{
avl.insert({ v[i],v[i] });
}
int end2 = clock();
if (rb.IsBalance() && avl.IsBalance())
{
cout << "插入" << N << "个数据" << "红黑树用时间" << end1 - begin1 << ' ' << "旋转次数:" << rb.RotateCount;
cout << endl;
cout << "插入" << N << "个数据" << "AVL树用时间" << end2 - begin2 << ' ' << "旋转次数:" << avl.Rotatecount;
}
return 0;
}
还可以去测试一下他们的高度，有序数据，随机数据，查找的效率等等。
总体来说，红黑树是更优秀的，数据量越大红黑树的优势就越明显。
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
五、完整代码
总结
红黑树很重要！！！！一定要牢牢掌握。
接下来map和set还需要使用它。