引言
之前学习的AVL树，是一种平衡二叉搜索树，它追求绝对平衡，从而导致插入和删除性能较差。而今天学习的红黑树，是另一种平衡二叉搜索树，它追求相对平衡，使得增删查改的性能都极佳，时间复杂度皆为O(log2N)，是数据结构中的精华，天才般的设想！
一、红黑树的概念
红黑树，顾名思义，其节点有红和黑两种颜色。
之所以新增结点颜色的标记，是因为通过结点着色方式的限制，能够让红黑树的最长路径不超过最短路径的两倍，以保证相对平衡。
红黑树满足五条性质：
- 所有结点非黑即红
- 根结点为黑色
- NIL结点为黑色
- 红色结点的子结点必为黑色
- 任意结点到其叶子NIL结点的所有路径，都包含相同的黑色结点
在红黑树中，NIL节点（也称为空节点）是叶子节点的一种特殊表示。它们不是实际存储数据的节点，而是树结构中的占位符，用于定义树的边界。所有的红黑树都以NIL节点为叶子节点，这些NIL节点在视觉上通常不被画出来。
性质解读：
- 性质4：表明不能有连续的红色结点
- 性质4+性质5：
- 理论最短路径：全为黑色结点
- 理论最长路径：红黑相间
这样，就保证了最长路径不超过最短路径的两倍。
二、红黑树的模拟实现
2.1 结点
enum Color { 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; Color _col; RBTreeNode(const pair<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(RED) {} };
细节：
- 使用三叉链，增加了指向parent的指针
- 使用KV模型，数据存储键值对pair
- 结点储存颜色，同时颜色使用枚举
- 结点的颜色初始化为红色
说明：为什么结点的颜色初始化为红色呢？因为插入新节点时（不为根部），如果插入黑色，就会直接破坏性质5，导致每条路径黑结点数目不同；而如果插入红色，有可能不会破坏性质4，所以结点初始化为红色更优。
2.2 成员变量
template<class K, class V> class RBTree { protected: typedef RBTreeNode<K, V> Node; public: protected: Node* _root = nullptr; };
2.3 插入
因为红黑树也是二叉搜索树，所以默认成员函数和遍历与之前写的没什么不同，这里重点讲解红黑树的插入。
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->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; if (grandparent->_right == parent)//uncle在左，parent在右 { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED)//uncle为红，变色+向上调整 { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = cur->_parent; } else//uncle为空或为黑，变色+旋转 { if (parent->_right == cur)//左单旋 { RotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else//右左旋 { RotateR(parent); RotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED; } } } else//parent在左，uncle在右 { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = cur->_parent; } else { if (parent->_left == cur)//右单旋 { RotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else//左右旋 { RotateL(parent); RotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; } } } } _root->_col = BLACK; return true; }
思路：
- 以二叉搜索树的方式正常插入
- 讨论并调整结点的颜色，以及调整结构，使之满足红黑树的性质
循环条件：while (parent && parent->_col == RED)
保证了parent存在且为红，grandparent存在且为黑
情况一：uncle在左，parent在右
如果uncle存在且为红色：
处理方法：
- 将parent和uncle变黑，grandparent变红
- cur = grandparent，parent = cur->_parent，继续向上调整
- 防止grandparent为根节点却变红，在循环结束后将根节点变为黑色
如果uncle不存在，或者存在且为黑色：
当cur在右部外侧时：
处理方法：
- 先对grandparent进行左单旋
- 再将parent变黑，grandparent变红
当cur在右部内侧时：
处理方法：
- 先对parent进行右单旋
- 再对grandparent进行左单旋
- 最后将cur变黑，grandparent变红
情况二：parent在左，uncle在右
如果uncle存在且为红色：
处理方法：
- 将parent和uncle变黑，grandparent变红
- cur = grandparent，parent = cur->_parent，继续向上调整
- 防止grandparent为根节点却变红，在循环结束后将根节点变为黑色
如果uncle不存在，或者存在且为黑色：
当cur在左部外侧时：
处理方法：
- 先对grandparent进行右单旋
- 再将parent变黑，grandparent变红
当cur在左部内侧时：
处理方法：
- 先对parent进行左单旋
- 再对grandparent进行右单旋
- 最后将cur变黑，grandparent变红
红黑树插入的核心口诀：uncle存在且为红，变色+向上调整，uncle不存在或为黑，变色+旋转
附上旋转的实现：
void RotateL(Node* parent) { Node* grandparent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; parent->_parent = subR; if (grandparent) { if (grandparent->_right == parent) { grandparent->_right = subR; } else { grandparent->_left = subR; } } else { _root = subR; } subR->_parent = grandparent; } void RotateR(Node* parent) { Node* grandparent = parent->_parent; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; parent->_parent = subL; if (grandparent) { if (grandparent->_right == parent) { grandparent->_right = subL; } else { grandparent->_left = subL; } } else { _root = subL; } subL->_parent = grandparent; }
三、红黑树的验证
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->_right; } return Check(_root, 0, benchMark); } bool Check(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 Check(root->_left, blackNum, benchMark) && Check(root->_right, blackNum, benchMark); }
细节：
- 验证根节点是否为黑
- 先计算出一条路径的黑色结点个数作为基准值，再在递归中比较每条路径的黑色结点是否相等
- 若该节点为红，检测其parent是否为红，判断是否存在连续的红色节点
四、红黑树的性能
4.1 优势
红黑树是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对AVL树而言，降低了插入和旋转的次数。
4.2 适用场景
因此，在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
真诚点赞，手有余香
