1. 红黑树的概念
2. 红黑树的插入
- 2.1. 情况1
- 2.2. 情况2
- 2.3. 情况3
- 2.4. 插入情况小总结
3. 红黑树与AVL树的对比
4. 红黑树在线生成网站

1. 红黑树的概念

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除操作时通过调整节点的颜色和旋转来保持树的平衡。红黑树的平衡性是通过以下规则来定义和维护的：

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶子节点（NIL节点，空节点）都是黑色。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（称为黑色高度）。

通过这些规则，红黑树能够保持相对平衡，从而保证了其插入、删除和查找等操作的时间复杂度都能够保持在O(log n)级别。

红黑树图：

关于性质的说明：

不可能出现连续两个红节点

这种情况是不允许的！

每条路径上的黑色节点数是相同的。

如图中的路径A与路径B，他们黑色节点数是相同的，如果违背了这些性质，红黑树的结构将会被破坏。

2. 红黑树的插入

红黑树本身是二叉搜索树，只不过是在其基础增加了颜色的区分。所以插入是跟二叉搜索树一样的，不过要根据红黑树的规则来调整。

插入大概上分为3种情况：

2.1. 情况1

cur为红，p为红，g为黑，u存在且为红

举个简单例子，如图：

这种情况违背了红黑树的规则，有两个连续的红节点，此时就需要调整。

把parent和uncle变为黑色
再把grandfather变为红色
把grandfa给给cur，再继续往上看是否需要调整

调整后的红黑树：

根据上面的情况分析给出抽象图：

**假设A/B/C/D/E为一个节点，那么C/D/E的节点将会是黑色的，而A/B是红色的。**具体为什么可以参考红黑树的规则想想。

如果此时选择插入一个节点，那么将会出现情况1。

那么此时具体图如下：

第一次调整如图：

第一次调整结束后，根据调整过程cur会变动，根据情况分析，此时还需要再一次调整。

第二次调整：

此时白色圆圈代表的是，这棵树可能只是一颗子树，如果不是子树的的话，根节点的颜色要变黑色。

根据抽象图来画具象图，会有很多种情况，但最主要的情况就是cur为红，p为红，g为黑，u存在且为红.

代码如下：

2.2. 情况2

cur红且为p左子树，p为红，g为黑，u不存在/u存在且为黑

先举抽象图例子：

当A/B/C/D/E都为空的时候，那么uncle节点是不可能存在的。**因为如果uncle此时存在的话，那么就是情况1，但这里讨论的是情况2，情况2要求的是uncle节点要么存在，要么不存在，而如果uncle存在的话，将不符合红黑树结构的要求。**具象图如下：

那么此时就是情况2的uncle节点不存在的情况。所需要做的就是进行右单旋操作。调整后如下图：

为什么旋转之后，颜色是这样子变化呢？我想要cur和grandfather的颜色为黑，parent为红不行吗？别急，答案在抽象图会出来。

当A/B/C/D/E的高度为1，并且cur节点的颜色为黑色，如下图所示：

调整后如下图：

此时这种情况就是情况2，要进行旋转，旋转后如下图：

总体的旋转如下图所示：

情况2的抽象图：

经过旋转，但是颜色未变的视图：

如上图所见，这里的grandfather节点颜色是不能为黑色的，因为不符合红黑树的结构规则，因此是要将grandfather和cur的颜色变为红色，而parent颜色为黑色，如下图所示：

代码如下：

2.3. 情况3

cur红且为p右子树，p为红，g为黑，u不存在/u存在且为黑

这里只画A/B/C/D/E为一个节点时的具象图。

具体来说就是，当A/B/C/D/E高度为1的时候，先是碰到了情况1，调整之后，变成了情况2，再调整后，又变成了另一个方向的情况2。那么就根据这种种情况，依次旋转即可。

代码如下：

最后要记得把根节点的颜色变为黑色：

代码实现：

bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_pRight;}else if (data < cur->_data){parent = cur;cur = cur->_pLeft;}else{return false;}}cur = new Node(data);if (data > parent->_data){parent->_pRight = cur;cur->_pParent = parent;}else if (data < parent->_data){parent->_pLeft = cur;cur->_pParent = parent;}//新插入的节点默认颜色为红色，所以下面cur颜色都为红while (parent && parent->_col == RED){Node* grandfather = parent->_pParent;if (parent == grandfather->_pLeft){Node* uncle = grandfather->_pRight;//情况1 p为红，g为黑，u为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_pParent;}//走到这里，uncle两种情况//1. uncle存在且为黑//2. uncle不存在else{//情况2//如果cur是parent左子树，进行右旋转if (cur == parent->_pLeft){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//情况3else if (cur == parent->_pRight){RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else if (parent == grandfather->_pRight){Node* uncle = grandfather->_pLeft;//情况1 p为红，g为黑，u为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_pParent;}//走到这里，uncle两种情况//1. uncle存在且为黑//2. uncle不存在else{//情况2//如果cur是parent左子树，进行右旋转if (cur == parent->_pLeft){RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//情况3else if (cur == parent->_pRight){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

2.4. 插入情况小总结

大类上分为两类，一是uncle节点为红色，而是uncle节点为黑色
根据uncle节点的颜色，又分为两种情况
如果uncle节点颜色为红色，并且parent节点和cur节点都为红色，那么就是情况1，直接变颜色即可
如果uncle节点颜色为黑色，并且parent节点和cur节点都为红色，cur是parent的左节点，那么就是情况2，单旋转
如果uncle节点颜色为黑色，并且parent节点和cur节点都为红色，cur是parent的右节点，那么就是情况3，双旋转
关键就是看uncle节点是否存在以及uncle节点的颜色

3. 红黑树与AVL树的对比

红黑树和AVL树都是常用的自平衡二叉搜索树，它们的主要目的都是为了保持树的平衡，以提高搜索、插入和删除操作的性能。然而，红黑树和AVL树在平衡的方式和性能方面存在一些差异。

平衡性：

- 红黑树：红黑树通过在节点上引入颜色属性，并遵循一组平衡规则来保持平衡。这些规则包括节点的颜色、路径上的黑色节点数量等。红黑树的平衡性相对较弱，可以在维护平衡的同时提供较高的插入和删除性能。
- AVL树：AVL树通过在节点上维护一个平衡因子（左子树高度减去右子树高度）来保持平衡。AVL树的平衡性相对较强，要求任何节点的平衡因子在-1、0、1之间。这种强平衡性保证了AVL树的高度始终保持在较小的范围内，但可能会导致插入和删除操作的性能稍低。

插入和删除操作：

- 红黑树：由于红黑树的平衡性相对较弱，插入和删除操作的性能较好。红黑树在执行这些操作时只需要进行一些颜色调整和旋转操作，时间复杂度为O(log n)。
- AVL树：由于AVL树的平衡性较强，插入和删除操作可能需要进行更多的旋转操作来保持平衡，因此性能略低于红黑树。插入和删除操作的时间复杂度为O(log n)。