暑假提升(3)[平衡二叉树之二--红黑树]

命为志存。 —— 朱熹

红黑树RBTree

1、诞生原因
2、红黑树的概念
3、红黑树的性质
4、红黑树的设计
- 4、1、节点设计
- 4、2、插入操作的设计
5、总结

1、诞生原因

由于二叉树的局限性，进一步出现平衡二叉树，来帮助我们来进一步提升我们对数据的处理，根据之前的文章，我能够理解其中的一种平衡二叉树(AVL树)能够帮助我们解决退化的问题。由于诞生原因那篇文章中讲过了，这里就不再赘述，所以接下来直接介绍红黑树其本身的概念和知识点，在最后还会讲一些一些关于红黑树的模拟实现。

2、红黑树的概念

红黑树，也是一种二叉搜索树，但是每一个节点上增加一个存储位置来表示节点的颜色。这又就是红黑树顾名思义，每一个节点存在着一个颜色来表示一个特征。为什么是红黑两种颜色，首先颜色种类无所谓，是两种都是可以的，其次选择两种颜色的原因还是因为在后续的控制树的树枝的时候能够保证一个节点的左右子树之间高度的绝对值差不会太大，保证树的接近平衡。所以通过对任意一条从根到叶子结点的路径上个个节点的着色限制，来保证红黑树确保没有一条路径会比其他路径长出两倍。

3、红黑树的性质

1、每一个节点不是红色就是黑色
2、根节点是黑色的
3、如果一个节点是红色的，那么他的孩子节点是黑色的(没代表黑色节点的孩子节点一定要是红色还是黑色)
4、对于每个节点，从该节点到所有后代叶节点的简单路径上，所包含黑色节点的个数相同
5、每个叶子结点都是黑色的(规定所有的叶子结点都是空节点)
所以根据上面的条件，能够推理出最长的路径一定是尽量的满足黑红黑红的排序方式，最短的路径一定是尽量满足“嘿嘿嘿”的排序方式。
所以在这样的要求之下，红黑树就是具有着能够优化二叉搜索树的特点。
那么，所以，红黑树虽然在规则上满足了能够解决二叉搜索树的缺点，那么插入的时候是如何实现的呢？
接下来我们来介绍一下。

4、红黑树的设计

4、1、节点设计

节点设计不难理解，如果是我的上一篇文章中看到这里的话，理解了AVLTreeNode的设计之后，想到RBTreeNode的结构和细节应该不成问题。
首先，可以先回顾一下AVLTreeNode的代码

template<class T>
struct AVLTreeNode
 {
 	AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
      ,_data(data), _bf(0)
    {}
 	AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
	AVLTreeNode<T>* _pRight;  // 该节点的右孩子
	AVLTreeNode<T>* _pParent; // 该节点的双亲
	T _data;
    int _bf; 
};

那么关于RVBTreeNode的大概形式和上一个相同，但是不同的就是这次里面还要加上颜色的成员来帮助我们实现节点。

enum Colour
{
	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;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

红黑树解释：
1、其中红黑颜色怎么在结构体种体现的问题，通过枚举类型来帮助解决。
2、我提供的代码之中，这种结构体的设计是KV的模型
3、在定义的时候利用到模版，方便与其他另外的KV模型的实现和改变。

==反思：==为什么每一个节点的设计都是默认的红色呢？
解答： 根据红黑树的性质来说，在加入节点之后，必须要按照规矩和性质来解决可能出现的一些导致性质出现和实际的红黑树有不同的地方。那么每一个节点的插入之后，必须要调整一下来保证还是能够让整个树都满足条件的。那么红色的默认设计就是会比黑色好得多。因为根据红黑树的性质中来讲的话，其中的条件四更加的严苛，条件三还能够相对而言还能够方便继续修改。 ==所以即使是破坏条件三，也不愿意破坏条件四。==那么，接下来的问题就是，为什么相比较而言，条件还有“谁轻谁重”的概念。==如果是插入红色的节点，可能会破坏条件三(在上一个节点是红色的情况之下的话)只是需要修改一下，从插入的节点向上修改一下，并且这一条路径修改好了之后呢，其余的稍微修改一下就行。(如果想看到底怎么修改，那么就看一下下面插入操作的设计，会包含所有的情况)。那么对于插入黑色节点的情况下，是一定会破坏条件四的，==一条路径上如果是直接加上一个黑色的节点，那么所有的路径之上，之前保持的黑色节点的平衡就不复存在，就需要修改每一个路径之上的所有的红黑节点的分配。
所以，在这样的情况之下的话想对比较而言的话，直接插入红色节点的消耗会比黑色的少很多，也更加容易实现红黑树的插入操作。

为了解决红黑树的插入操作的细节的问题，接下来要具体讲一下关于插入的模拟实现，这样既能够实现插入操作，也能知晓插入的一些注意事项。

4、2、插入操作的设计

与AVLTree树不同的是，没有了平衡因子，只有颜色的成员。那么该怎么合理的解决问题呢？
由于红黑树其实本质上来说就是满足性质的二叉树。所以，在插入的时候，可以大致的分为两种情况(直接分为两种情况是因为这两种情况下的子问题，是能够通过相同的解决方案来解决的)。
哦哦哦！对了，在插入节点的判断开始之前，需要判断一下是否是头节点，如果是头节点的插入的话不需要考虑太多，只需要设置这个节点为头节点并且设置一下节点的颜色，把他设置为黑色的。
接下来先介绍一下前提，cur节点的意思可以宽泛一点的认为是cur以下节点更新完之后的节点，p节点的意思是cur节点的父亲节点，g节点是cur父亲节点的父亲节点，u节点是g节点的孩子节点(不是p节点)
如果是根节点的情况而停止向上的话，那么我们就需要重新的更新一下根节点的颜色，重新变为黑色，因为要满足性质。
情况一：如果u节点存在并且为红色。
在这里插入图片描述
这就是第一种情况，此时p需要和u一起更新为黑色，然后g再变为红色，判断是否需要继续循环，然后再下一步。是否循环的条件就是p节点为红并且p节点存在就继续向上更新。
情况二： u节点不存在/存在且为黑色。
在这里插入图片描述