（一）红黑树的定义
1、红黑树的引入
为了保持 AVL 树的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价较大。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构。
2、红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。
3、红黑树的性质
一棵红黑树是满足如下红黑性质的二叉排序树：
- ①每个结点或是红色，或是黑色的
- ②根结点是黑色的
- ③叶结点（虚构的外部结点、 NULL 结点）都是黑色的
- ④不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）
- ⑤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同
与折半查找树和 B 树类似，为了便于对红黑树的实现和理解，引入了 n +1个外部叶结点，以保证红黑树中每个结点（内部结点）的左、右孩子均非空。下图所示是一棵红黑树：
从某结点出发（不含该结点）到达一个叶结点的任一简单路径上的黑结点总数称为该结点的黑高（记为 bh )，黑高的概念是由性质⑤确定的。根结点的黑高称为红黑树的黑高。
结论1：从根到叶结点的最长路径不大于最短路径的2倍。
- 由性质⑤，当从根到任一叶结点的简单路径最短时，这条路径必然全由黑结点构成；
- 由性质④，当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时红结点和黑结点的数量相同；
- 上图中的 13-8-1 和13 - 17 - 25 - 27就是这样的两条路径。
结论2：有n个内部结点的红黑树高度 h <=2log(N+1)
由此可见，红黑树的"适度平衡"，由 AVL 树的"高度平衡"，降低到"任一结点左右子树的高度，相差不超过2倍"，也降低了动态操作时调整的频率。对于一棵动态查找树，如果插入和删除操作比较少，查找操作比较多，采用 AVL 树比较合适，否则采用红黑树更合适。但由于维护这种高度平衡所付出的代价比获得的效益大得多，红黑树的实际应用更广泛， C +＋中的 map 和 set ( Java 中的 TreeMap 和 TreeSet ）就是用红黑树实现的。
（二）红黑树的操作
1、红黑树节点的定义
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) {} };
思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
红黑树是一种自平衡的二叉搜索树，它通过在插入和删除节点时进行一系列的旋转和重新着色操作来维持平衡性质。根据红黑树的性质，每个节点要么是红色，要么是黑色。
在红黑树的插入和删除操作中，为了保持树的平衡，需要对节点进行旋转和着色。将新插入的节点默认着色为红色有以下几个原因：
- 红色节点具有更多的调整空间：将节点默认着色为红色，可以让新节点具有更多的调整空间，有利于保持树的平衡性。红色节点的插入和删除操作对树的平衡影响较小，因为红色节点可以在需要时进行旋转和着色调整。
- 简化插入操作的修正过程：新节点默认为红色，可以简化插入操作的修正过程。根据红黑树的性质，插入红色节点后只需要考虑和父节点的关系，而不需要像黑色节点那样考虑更多的调整情况。这样可以减少修正操作的复杂性和开销。
- 减少整体平衡操作的次数：将新节点默认设置为红色，可以减少整体平衡操作的次数。由于红色节点的插入和删除操作对树的平衡影响较小，相比于将新节点默认设置为黑色，将其默认设置为红色可以减少平衡操作的频率和开销。
总的来说，将节点的默认颜色设置为红色是为了在红黑树等自平衡数据结构中简化插入和删除操作的修正过程，同时减少整体平衡操作的次数，提高了算法的效率和性能。
2、红黑树的插入操作
1?? 思路
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
- 1.按照二叉搜索的树规则插入新节点（这个我们之前说过，这里就不过多解释了）
- 2.检测新节点插入后，红黑树的性质是否造到破坏（重点讲解）
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
- 情况一: cur为红，p为红，g为黑，u存在且为红
解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整
- 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
1.p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
2.p为g的右孩子，cur为p的右孩子，则进行左单旋转
3.p、g变色--p变黑，g变红
- 情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑
针对每种情况进行相应的处理即可
2?? 代码实现
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); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //进行调整操作 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在/u存在且为黑，旋转+变色 { // g // p u // c if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; //parent->_col = RED; grandfather->_col = RED; } break; } } else // (grandfather->_right == parent) { // g // u p // c Node* uncle = grandfather->_left; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在/u存在且为黑，旋转+变色 { // g // u p // c if (cur == parent->_right) { RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }
3、红黑树的删除操作（了解）
红黑树的删除本节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》
4、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
5、红黑树的验证
红黑树的检测分为两步：
- 1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 2. 检测其是否满足红黑树的性质
void Inorder() { _Inorder(_root); } bool IsBalance() { if (_root && _root->_col == RED) { cout << "根节点颜色是红色" << endl; return false; } int benchmark = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++benchmark; cur = cur->_left; } // 连续红色节点 return _Judge(_root, 0, benchmark); } bool _Judge(Node* root, int blackNum, int benchmark) { if (root == nullptr) { if (blackNum != benchmark) { cout << "某条路径黑色节点的数量不相等" << endl; return false; } return true; } if (root->_col == BLACK) { ++blackNum; } if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << "存在连续的红色节点" << endl; return false; } return _Judge(root->_left, blackNum, benchmark) && _Judge(root->_right, blackNum, benchmark); }
总结
以上便是关于红黑树的介绍。感谢大家的观看与支持！！！
