[C++进阶数据结构]红黑树(半成品)

我们讲完了AVL树,它追求绝对平衡，从而导致插入和删除性能较差。今天我们来讲讲，红黑树，它是另一种平衡二叉搜索树，它追求相对平衡，使得增删查改的性能都极佳，时间复杂度皆为O(log2N)。

一、红黑树的概念

1.红黑树的概念

红黑树，顾名思义，其节点有红和黑两种颜色。

之所以新增结点颜色的标记，是因为通过结点着色方式的限制，能够让红黑树的最长路径不超过最短路径的两倍，以保证相对平衡。

红黑树满足五条性质：

所有结点非黑即红
根结点为黑色
NIL结点为黑色
红色结点的子结点必为黑色
任意结点到其叶子NIL结点的所有路径，都包含相同的黑色结点

在红黑树中，NIL节点（也称为空节点）是叶子节点的一种特殊表示。它们不是实际存储数据的节点，而是树结构中的占位符，用于定义树的边界。所有的红黑树都以NIL节点为叶子节点，这些NIL节点在视觉上通常不被画出来

2.红黑树的性质

上面讲的不够详细这里我接着补充

红黑树的结点的旋转是和颜色息息相关

首先我们先来看这个红黑树：

这红黑树有：

11条路径(注意是11条因为空节点也包括在内)

如果没懂，我们来看下面这棵：

是不是有人认为这是红黑树了？

实际上它不是红黑树。

如果我们不看每个空结点的话，它看上去有四条路径，且每条路径都只有两个黑色结点，看上去好像是红黑树。但是实际上要包括空结点，且空结点是黑色的。所以一共有九条路径，最左边的一条路径只有两个黑色结点，其他路径都有三个黑色结点。

每个结点的每条路径上的黑色结点个数相同，但是由于每个结点的祖先的路径是唯一确定的，所以我们只需要判断从根节点到每个空结点上的路径中黑色结点个数是否相同即可。

但是我们知道最长路径不超过最长路径的两倍，这个性质该怎么解决呢？

其实我们只要保证每个结点的每条路径上的黑色结点个数相同，该性质就成立了！

3.红黑树和AVL树的对比

既然有了AVL树，那么为什么要有红黑树呢？其实是因为AVL树太严格了。它要控制平衡就需要付出代价。而红黑树要求并不严格，综合来看，红黑树的综合性能其实更优

树	AVL树	红黑树
高度对比	高度差不超过一	最长路径不超过最短路径的两倍
插入1000个值	logN---->10	2*logN---->20
插入10亿个值	logN---->30	2*logN---->60

我们可以看到，虽然他们的高度有点差异，但是他们的效率都是同一个量级的，而且cpu的速度是非常快的，这点效率对于cpu几乎没有任何区别

性能是同一量级的，但是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;Color _col;RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

细节：

使用三叉链，增加了指向parent的指针
使用KV模型，数据存储键值对pair
结点储存颜色，同时颜色使用枚举
结点的颜色初始化为红色

说明：为什么结点的颜色初始化为红色呢？因为插入新节点时（不为根部），如果插入黑色，就会直接破坏性质5，导致每条路径黑结点数目不同；而如果插入红色，有可能不会破坏性质4，所以结点初始化为红色更优。

2. 成员变量

template<class K, class V>
class RBTree
{
protected:typedef RBTreeNode<K, V> Node;
public:
protected:Node* _root = nullptr;
};

3.插入

1) 红黑树的结点定义

红黑树有红色结点和黑色结点两种颜色。所以不妨我们使用一个枚举类型来进行表示。红黑树里面我们需要有一个pair类型来进行存储key和value类型的数据。然后我们定义三个指针，分别指向父亲，左孩子，右孩子。最后定义其的颜色。在构造函数中，我们将其的颜色默认设置为红色。

设置为红色是比较有讲究的。那是因为我们大多数场景下都是去创建一个新节点去插入的。如果我们插入的这个新结点是黑色的话，那么造成的后果就是违反了规则4，即每条路径上的黑色结点个数相同，显然这种情况要进行补救的话是十分麻烦的。还不如去插入红色结点，如果插入的是红色结点的话，仅仅有可能会违反规则3，也就是红色结点的孩子必须是黑色结点。这一点的话，我们还有的补救，因为仅仅影响本条路径。

enum Color
{RED,BLACK
};template<class K , class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_color(RED) // 插入红色结点，违反规则3，只影响一条路径，甚至可能不影响。如果插入黑色结点，违反规则4，影响所有路径{}
};

2)父亲的颜色

因为我们要插入的结点是红色的，那么在我们插入的位置，它的父亲要么是红色的要么是黑色的。如果是黑色的，如下:

我们可以看到，似乎并未影响整棵树的结构，不违反任何一条规则。最短路径仍然不超过最长路径的两倍。每条路径上的黑色结点个数仍然相等。所以如果插入一个新节点以后，如果此处它的父亲是黑色的，完美，不需要做出任何修改即可。如果父亲甚至都不存在，那么这个结点就是这颗树了。我们只需要将这个结点变为黑色即可。如果父亲是红色的话，那么就比较麻烦了。

如下图所示，此时我们需要对这颗树进行处理了。

3. 叔叔的颜色为红色

如果我们插入了一个结点以后，此时，父亲结点为红色，且有父亲的兄弟，即叔叔，且叔叔的颜色是红色。

即如下的情况，uncle存在且为红

这样的话，我们可以将parent和uncle都变黑，然后让grandfather变红，即如下的情形

这样的话，在黑色结点数量不变的条件下，使得连续红色结点的问题暂时解决了。现在原本cur为红色的问题转换为了grandfather为红色的问题。

此时的话，如果这个grandfather如果没有父亲了，那么根据规则1，我们只需要让他变为黑色即可。此时仅仅只是所有的路径多了一个黑色结点。如果grandfather有父亲，那么我们只需要让grandfather变为cur，继续向上处理即可

在这里继续向上处理的时候又分为以下几种情况:

grandfather没有父亲，那么直接让grandfather变黑即可
grandfather有父亲，且父亲为黑色，那么由于前面的树本身就是满足红黑树规则，这里改变了之后仍然满足红黑树规则，那么不处理即可
grandfather有父亲，且父亲为红色，这样的情况下，父亲为红色，就隐含了必然存在grandfather的grandfather，因为原来的树也要满足红黑树的规则，这样一来就是类似的问题继续往处理即可。