【C++第二十章】红黑树

红黑树介绍🧐

  红黑树是一种自平衡的二叉搜索树，通过颜色标记和特定规则保持树的平衡性，从而在动态插入、删除等操作中维持较高的效率。它的最长路径不会超过最短路径的两倍，它的查找效率比AVL树更慢(对于CPU来说可以忽略不计)，但是它不会像AVL树那样花费更大的代价去实现严格平衡(旋转)。

1.红黑树与AVL树🔎

特性 红黑树 AVL树
平衡标准 通过颜色规则约束，允许一定不平衡严格平衡（左右子树高度差≤1）
插入/删除效率 旋转次数少，调整频率低可能需要多次旋转，调整频率高
查询效率 平均稍慢（高度≤2log(n+1)）更快（高度严格为O(log n)）
适用场景 频繁插入/删除（如内存数据库、STL Map）查询密集（如字典、静态数据集）
实现复杂度 较复杂（需处理颜色标记和多种情况）相对简单（仅维护平衡因子）

2.设计思想🔎

平衡与效率的折衷：
红黑树通过放宽平衡条件（允许局部不平衡），减少插入/删除时的调整次数，适合写多读少的场景。AVL树追求绝对平衡，适合读多写少的场景。
模拟B树结构：
红黑树可视为一种“二叉化”的B树（如2-3-4树），每个节点隐含多个键值，通过颜色标记合并逻辑，减少树的高度。
工业界应用：
红黑树：Java的 TreeMap、C++的 std::map、Linux内核调度器。
AVL树：Windows内核对象管理、需要快速查找的静态数据库。

  所以，若需要高频插入/删除，我们可以选择红黑树，若需要快速查询，不怎么变动数据，选择AVL树。

3.红黑树的性质🔎

每个节点不是红色就是黑色。
根节点一定是黑色的。
如果一个节点是红色的，则它的两个孩子节点是黑色的。(不能出现连续的红色节点)。
对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。(每条路径黑色节点数量相同)。
每个叶子节点都是黑色的(这里的叶子节点指的是空指针节点，也称NIL节点)

  其中，路径的条数是从根节点到NIL节点来计算的，并且NIL节点的黑色也要统计到每条路径的黑色节点数量中。红黑树的最长和最短路径不一定存在。

特性	红黑树	AVL树
平衡标准	通过颜色规则约束，允许一定不平衡	严格平衡（左右子树高度差≤1）
插入/删除效率	旋转次数少，调整频率低	可能需要多次旋转，调整频率高
查询效率	平均稍慢（高度≤2log(n+1)）	更快（高度严格为O(log n)）
适用场景	频繁插入/删除（如内存数据库、STL Map）	查询密集（如字典、静态数据集）
实现复杂度	较复杂（需处理颜色标记和多种情况）	相对简单（仅维护平衡因子）

红黑树插入实现🧐

红黑树的平衡方式为：直接变色、旋转变色，所以我们还是要用到AVL树中的旋转代码。

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; //这里使用的是KV模型Color _col; //颜色RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) //默认设置为红色，如果默认为黑色，则每次插入必定违反性质4{}
};

2.左单旋、右单旋🔎

与AVL树中一摸一样的方法。

//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根parent->_parent = subR;if (subRL) //subRL不为空才处理subRL->_parent = parent;if (_root == parent) //当parent就是整个树的根，直接改变{_root = subR;subR->_parent = nullptr;}else{//如果不是，结点在父左边就将左边置为subR，否则右边if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent; //父节点也要改变}
}//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //subLR不为空才处理subLR->_parent = parent;//放在subL下面，不然parentParent可能为空Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根subL->_right = parent;parent->_parent = subL;if (_root == parent) //当parent就是整个树的根，直接改变{_root = subL;subL->_parent = nullptr;}else{//如果不是，结点在父左边就将左边置为subL，否则右边if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent; //subL父节点也要改变}
}

3.插入🔎

我们在节点定义时就将默认颜色设置为红色，是因为将默认颜色设置为黑色的话，那么一个正常的红黑树突然插入一个黑色必定违反性质4，则每次都需要调整。

而插入红色时我们进行分析得：

1.当插入节点的父亲节点为黑色时，没有违反任何性质，不需要处理。

2.当插入节点的父亲节点为红色时，违反性质3，需要处理。

由此再次对红黑树分情况讨论：

我们首先约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

解决方法：

将p，u改为黑，g改为红，如果g是根节点，那么再改为黑，如果不是根节点且违反性质4，那么将g看为cur，再次进行调整。

情况二：cur为红，p为红，g为黑，u不存在或者u存在且为黑

解决方法：

如果p是g的左孩子，cur为p的左孩子，则进行右单旋；如果p是g的右孩子，cur为p的右孩子，则进行左单旋。然后进行p、g变色，p变黑，g变红。

情况三：cur为红，p为红，g为黑，u不存在或者存在且为黑。

解决方法：

如果p是g的左孩子，cur为p的右孩子，则进行左单旋；如果p是g的右孩子，cur为p的左孩子，则进行右单旋。然后转换为情况二处理。

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 (parent->_kv.first < kv.first)
{parent->_right = cur;cur->_parent = parent;
}
else
{parent->_left = cur;cur->_parent = parent;
}// 父亲为红色，需要处理
while (parent && parent->_col == RED)
{Node* grandfather = parent->_parent; if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 叔节点存在且为红（颜色翻转）if (uncle && uncle->_col == RED)、{//    g//   p u//  c//变色parent->_col = uncle->_col = BLACK; // 父叔变黑grandfather->_col = RED; // 祖父变红//继续往上处理cur = grandfather;parent = cur->_parent;}// 叔节点不存在或为黑（需要旋转）else{// 当前节点是父的左孩子if (cur == parent->_left){//     g//    p//   cRotateR(grandfather);parent->_col = BLACK; // 原父节点变黑grandfather->_col = RED; //祖父变红}// 当前节点是父的右孩子else{//     g//    p//     cRotateL(parent); // 先左旋父节点转换为情况二RotateR(grandfather);cur->_col = BLACK; //当前节点变黑grandfather->_col = RED; //祖父变红}break; // 旋转后子树平衡，退出循环}}// 父节点是祖父的右孩子else{//    g//   u p//      cNode* uncle = grandfather->_left;// 叔节点存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}// 叔节点不存在或为黑else{// 当前节点是父的右孩子if (cur == parent->_right){//     g//      p//       cRotateL(grandfather); // 左旋祖父节点parent->_col = BLACK;grandfather->_col = RED;}// 当前节点是父的左孩子else{//     g//       p//     cRotateR(parent); // 先右旋父节点转换为情况二RotateL(grandfather); // 再左旋祖父节点grandfather->_col = RED;cur->_col = BLACK;}break;}}
}
_root->_col = BLACK; //直接根变黑，不在需要考虑根的颜色问题return true;
}

4.平衡检测🔎

//根节点到当前结点的黑色数量
bool Check(Node* root, int blacknum, const int refVal)
{if (root == nullptr){if (blacknum != refVal){cout << "存在黑色结点数量不相等的路径!" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){//当两个结点都为红，就出问题了cout << "有连续的红色" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);
}bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED)return false;int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);
}