前言
红黑树和BST树、AVL树一样，都是带有排序性质的树。那么与这两种树不同的地方在哪？为什么在C++STL中的set和map都使用的红黑树？都将在阅读完这篇文章之后理解。
文章目录
一、红黑树的定义
- 每一个节点都是有颜色的，不是黑色就是红色。
- 根节点root必须是黑色的。
- 所有叶子节点都是黑色的，叶子节点是NULL节点，不存储实际的数据。
- 每个红色节点必须有两个黑色的子节点，或者说是从每个叶子节点到根节点的所有路径上不能有连续的红色节点。
- 从任一节点到其每个叶子上的所有简单路径都包含相同数目的黑色节点。
二、红黑树节点的定义
因为每个节点不是红色就是黑色，所以需要定义一个颜色相关的枚举量。
还需要操作其父节点，所以定义一个parent指针。
template<typename _Ty>
class RBTree
{
private:
// 节点颜色
enum Color
{
BLACK,
RED
};
// 节点定义
struct Node
{
Node(_Ty data = _Ty(), Node* left = nullptr,
Node* right = nullptr, Node* parent = nullptr,
Color color = BLACK)
: val_(data)
, left_(left)
, right_(right)
, parent_(parent)
, color_(color)
{}
_Ty val_;
Node* left_;
Node* right_;
Node* parent_; // 指向当前节点的父节点
Color color_; // 当前节点的颜色
};
Node* root_;
};
三、红黑树的插入理论讲解
- 如果是一个空树：则插入节点是黑色。
- 如果树非空，插入的新节点：红色！
此时要检查父节点颜色，如果父节点是黑色，插入完成；
如果父节点是红色，则出现连续的红色节点，就要开始做红黑树的插入调整操作：
情况1
父节点是红色，爷爷节点是黑色，且三者在同一侧。
如图新插入的节点C，如果父节点是红色，则为了保持红黑树的第4条性质，需要交换父亲节点和爷爷节点的颜色：
从局部图来看，这样似乎没错，但考虑不周，在这里还需要考虑爷爷节点的另一个孩子节点，这里叫作叔叔节点，如果叔叔节点本身为红色，那么经过这样交换后，又不满足红黑树性质了。所以正确的情况为：
即使到了这一步，也不要觉得完成了，我们把新节点的爷爷节点的颜色改成红色了，这时候还需要考虑两种情况
- 如果爷爷节点的父节点也是红色，那又不满足红黑树性质，将x指向爷爷节点，继续调整。
- 爷爷节点是根节点，则强制将根节点置为黑色。
情况2
插入节点的父节点是红色，爷爷节点是黑色，三者在同一侧，叔叔节点是黑色。
为了满足红黑树性质，需要将其父节点颜色与爷爷节点颜色进行交换。
出现的问题：将爷爷节点A改成红色，那么就会导致从根节点到节点D的这条路径中，少一个黑色节点。不满足红黑树第5条性质（所有路径的黑色节点数量相等）。
解决方案：以A节点为参数做右旋转操作，旋转完成后，符合红黑树的性质，调整完成。
情况3
父节点是红色，爷爷节点是黑色，三者不在一侧，叔叔节点是黑色。
如图：如果直接调整颜色，那么还是会影响红黑树的第5个性质，所以可以先将三者旋转成同一侧，显然，这里需要对父节点B做左旋转，旋转后如图
将其旋转完成后，ABC处于同一侧，这时候再说如何改变颜色，但通过观察，旋转完成后，变成和情况2是一个情况，所以直接让其转到情况2的操作：
上面的三种情况，都是插入的节点在爷爷节点的左孩子上，那么与之对应的，右边也有相应的三种情况，所以红黑树的插入调整，一共有六种操作。
总结：红黑树的插入最重要的是考虑叔叔节点的颜色。
四、前置函数
// 返回节点颜色
Color getColor(Node* node)
{
return node == nullptr ? BLACK : node->color_;
}
// 设置颜色
void setColor(Node* node, Color color)
{
node->color_ = color;
}
// 返回节点的左孩子
Node* getLeft(Node* node)
{
return node->left_;
}
// 返回节点的右孩子
Node* getRight(Node* node)
{
return node->right_;
}
// 返回节点的父节点
Node* getParent(Node* node)
{
return node->parent_;
}
五、旋转操作详解
左旋转操作
如图，对node进行左旋转操作，它和AVL树的左旋转有什么区别？
AVL树左旋转代码：
// 左旋转操作
void leftRotate(Node* node)
{
Node* child = node->right_;
node->right_ = child->left_;
child->left_ = node;
}
由于红黑树多出了parent指针，所以在旋转时，要更改六个地址：
加上对parent操作的代码：
- 让child的parent指向node本身的parent，如果node的parent为NULL，则说明node就是根节点，则直接将根节点指向child；
- 如果node的parent不为NULL，则让node的parent的左孩子或右孩子指针指向child；
- 接下来更改child的左孩子，如果存在左孩子，就将左孩子的parent指针指向node；
- 最后更改node的parent指针，将其指向child。
// 左旋转操作
void leftRotate(Node* node)
{
Node* child = node->right_;
child->parent_ = node->parent_;
if (node->parent_ == nullptr)
{
root_ = child;
}
else
{
if (node->parent_->left_ == node)
{
// node在父节点的左孩子
node->parent_->left_ = child;
}
else
{
// node在父节点的右孩子
node->parent_->right_ = child;
}
}
node->right_ = child->left_;
if (child->left_ != nullptr)
{
child->left_->parent_ = node;
}
child->left_ = node;
node->parent_ = child;
}
右旋转操作
代码实现和左旋转刚好相反
// 右旋转
void rightRotate(Node* node)
{
Node* child = node->left_;
child->parent_ = node->parent_;
if (node->parent_ == nullptr)
{
// node原来就是root节点
root_ = child;
}
else
{
if (node->parent_->left_ == node)
{
node->parent_->left_ = child;
}
else
{
node->parent_->right_ = child;
}
}
node->left_ = child->right_;
if (child->right_ != nullptr)
{
child->right_->parent_ = node;
}
child->right_ = node;
node->parent_ = child;
}
六、插入操作代码实现
基于BST树的插入代码
// 插入操作
void insert(const _Ty& data)
{
if (root_ == nullptr) // 1
{
root_ = new Node(data);
return;
}
Node* parent = nullptr; // 2
Node* cur = root_; // 3
while (cur != nullptr)
{
if (cur->val_ > data) // 4
{
parent = cur;
cur = cur->left_;
}
else if (cur->val_ < data) // 5
{
parent = cur;
cur = cur->right_;
}
else
{
return; // 遇到重复的，则什么都不做 // 6
}
}
// 设置当前节点的parent和颜色
Node* node = new Node(data, nullptr, nullptr, parent, RED); // 7
if (parent->val_ > data)
{
parent->left_ = node;
}
else
{
parent->right_ = node;
}
// 如果新插入的红色节点，父节点也是红色，
// 则不满足红黑树性质，进行插入调整操作
if (RED == getColor(parent)) // 8
{
fixAfterInsert(node);
}
}
- 如果根节点为nullptr，则以data为根节点的值，构建根节点；
- parent指针，跟踪当前节点；
- cur指针，初始化指向根节点，查找的作用，用来找待插入位置；
- 如果cur的值大于待插入元素，则让parent指针指向当前节点，当前节点向左子树走；
- 如果cur的值小于待插入元素，则让parent指针指向当前节点，当前节点向右子树走；
- 上面两个情况不满足，说明遇到重复值了，直接退出；
- 申请新节点，设置新节点的指针域和颜色，新节点都为红色。再根据与当前parent节点的值域大小关系，将其挂到左子树或右子树上面；
- 插入完成后，就会面临上面提到的六种情况，涉及到更改颜色和旋转操作，这里写一个函数专门实现。
插入调整操作
该函数的作用就是在进行插入完成后，为了保证红黑树性质，所做出的调整（修正）操作，涉及更改颜色，旋转操作。
// 红黑树的插入调整操作
void fixAfterInsert(Node* node)
{
// 如果当前红色节点的父节点也是红色
while (RED == getColor(getParent(node))) // 1
{
// 如果当前节点的父节点是爷爷节点的左孩子
if (getLeft(getParent(getParent(node))) == getParent(node)) // 2
{
// 插入的节点在左子树
// 找到叔叔节点，改变颜色
Node* uncle = getRight(getParent(getParent(node))); // 3
if (RED == getColor(uncle)) // 情况1：叔叔节点是红色
{
setColor(uncle, BLACK);
setColor(getParent(node), BLACK);
setColor(getParent(getParent(node)), RED);
// 继续调整上面的
node = getParent(getParent(node)); // 4
}
else
{
// 先处理情况三，转成情况二
if (getRight(getParent(node)) == node) // 5
{
node = getParent(node);
leftRotate(node);
}
// 6 处理情况二
setColor(getParent(node), BLACK);
setColor(getParent(getParent(node)), RED);
rightRotate(getParent(getParent(node)));
break; // 调整完成
}
}
else // 7
{
// 插入的节点在右子树
Node* uncle = getLeft(getParent(getParent(node)));
if (RED == getColor(uncle)) // 情况1：叔叔节点是红色
{
setColor(uncle, BLACK);
setColor(getParent(node), BLACK);
setColor(getParent(getParent(node)), RED);
// 继续调整上面的
node = getParent(getParent(node));
}
else
{
// 先处理情况三，转成情况二
if (getLeft(getParent(node)) == node)
{
node = getParent(node);
rightRotate(node);
}
// 处理情况二
setColor(getParent(node), BLACK);
setColor(getParent(getParent(node)), RED);
leftRotate(getParent(getParent(node)));
break; // 调整完成
}
}
}
// 强制root_为黑色
setColor(root_, BLACK); // 8
}
这里可以配合上面的图片来理解：
- 使用一个while循环，用来判断当前节点的父节点是否是红色，因为在更改完成后，染成红色的节点的父节点有可能还是红色；
- 如果当前节点的父节点是爷爷节点的左孩子，则就是上面讲解的三种情况之一，处理这三种情况即可；
- 先利用一个uncle指针记录叔叔节点，如果叔叔节点是红色，则说明是情况1，处理操作：（1）将父节点置为BLACK，（2）将叔叔节点置为BLACK，（3）将爷爷节点置为RED。
- 将node指针指向爷爷节点，继续循环 向上调整；
- 如果叔叔节点是黑色，则属于第2，3种情况。这里先处理第3种，因为第3种情况可以转化为第2种。处理操作：判断当前节点是否是父节点的右孩子，如果是，则让node指向父节点，对父节点进行左旋转操作；
- 然后集中处理第2种情况：（1）将父节点置为BLACK，（2）将爷爷节点置为RED，（3）对当前点的爷爷节点进行右旋转操作，（4）跳出循环，执行第8步操作；
- else为其他三种情况，即插入节点在爷爷节点的右边，这里的操作与上面刚好相反，只需要更改与方向相关的操作即可；
- 为保证红黑树性质，结束时强制将根节点置为BLACK。
红黑树删除理论讲解（待补充）
本文含有隐藏内容，请 开通VIP 后查看