1. 红黑树的引入和简介
前面学了AVL树，平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logN)。AVL树的效率就是高在这个地方。
如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理,那么创建一颗平衡二叉树的成本其实不小。
这个时候就有人开始思考，并且提出了红黑树的理论，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 set和map 均是基于红黑树结构实现的。
那么红黑树到底比AVL树好在哪里？AVL树对平衡的要求太严格了，以至于它更多的会用到旋转，下面学的红黑树对平衡的要求就没有这么严格，所以它不会用到太多旋转。
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（最长路径不超过最短路径的两倍）
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明在当时被称为平衡二叉 B 树(symmetric binary B-trees)。
后来，在1978年被 Leo J. Guibas 和Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树二是一种接近平衡的叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5个性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。
2. 红黑树的性质和定义
红黑树是怎么保证最长路径不超过最短路径的两倍的？
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个空结点都是黑色的（这里的空结点也叫NIL结点，只是为了方便知道有多少条路径）
思考：为什么满足上面的性质，红黑树就能保证：最长路径不超过最短路径的两倍？
因为上面的性质形成了互斥：
最短路径：路径上全是黑色结点。
最长路径：红黑交替，黑色结点和红色结点的个数相等。
因为每条路径黑色结点个数是一样的，所以最长路径不超过最短路径的两倍。
红黑树的定义RedBlackTree.h:
#pragma once #include <iostream> using namespace std; 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; // 比AVL树少了平衡因子，多了颜色 RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) {} }; template<class K, class V> struct RBTree { typedef RBTreeNode<K, V> Node; protected: Node* _root = nullptr; };
3. 红黑树的插入
插入结点如果让你插入你是会插入红色结点还是黑色结点？
当我们向红黑树插入结点时，若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。
若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。
总结一下：
插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。
插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。
权衡利弊后，我们在构造结点进行插入时，将结点的颜色设置为红色。
红黑树插入结点的逻辑分为三步：
按二叉搜索树的插入方法，找到待插入位置。
将待插入结点插入到树中。
若插入结点的父结点是红色的，则需要对红黑树进行调整。
其中前两步与二叉搜索树插入结点时的逻辑相同，红黑树的关键在于第三步对红黑树的调整。
实际上，在插入结点后并不是一定会对红黑树进行调整，若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整，因为本次结点的插入并没有破坏红黑树的五点性质。
只有当插入结点的父结点是红色时才需要对红黑树进行调整，因为我们默认插入的结点就是红色的，如果插入结点的父结点也是红色的，那么此时就出现了连续的红色结点，因此需要对红黑树进行调整。
因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。
红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。
这里定义：cur为当前节点，p为parent父节点，g为grandfather祖父节点，u为uncle叔叔节点。
以下三种情况都是cur为红，p为红，g为黑，然后看叔叔的情况
3.1 调整情况一
调整情况一：插入结点的叔叔存在，且叔叔的颜色是红色。
此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。
但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。
因此，情况一的抽象图表示如下：
注意： 叔叔存在且为红时，cur结点是parent的左孩子还是右孩子，调整方法都是一样的。
情况一解决方法简记：将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父（cur）parent继续向上调整。
3.2 调整情况二
调整情况二：插入结点的叔叔存在，且叔叔的颜色是黑色。
需要注意：从根结点一直走到空位置就算一条路径，而不是从根结点走到左右结点均为空的叶子结点时才算一条路径。
情况二和情况三均需要进行旋转处理，旋转处理后无需继续往上进行调整，所以说情况二一定是由情况一往上调整的过程中出现的。出现叔叔存在且为黑时，单纯使用变色已经无法处理了，这时我们需要进行旋转处理。
3.2.1 调整情况二中的单旋+变色
若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。
抽象图表示如下：
此时parent是grandfather的左孩子，cur也是parent的左孩子时，
另一种情况：当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。
3.2.2 调整情况二中的双旋+变色
若祖孙三代的关系是折线（cur、parent、grandfather这三个结点为一条折线），则我们需要先进行双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。
抽象图表示如下：
此时parent是grandfather的左孩子，cur也是parent的右孩子时，左右双旋：
另一种情况： 当折线关系为，parent是grandfather的右孩子，cur是parent的左孩子时，就需要先进行右左双旋操作，再进行颜色调整。
3.3 调整情况三
调整情况三：插入结点的叔叔不存在。
在这种情况下的cur结点一定是新插入的结点，而不可能是由情况一变化而来的，因为叔叔不存在说明在parent的下面不可能再挂黑色结点了，如下图：
如果插入前parent下面再挂黑色结点，就会导致图中两条路径黑色结点的数目不相同，而parent是红色的，因此parent下面自然也不能挂红色结点，所以说这种情况下的cur结点一定是新插入的结点。
和情况二一样，若祖孙三代的关系是直线（cur、parent、grandfather 这三个结点为一条直线）则需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。
抽象图表示如下：
另一种情况：当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。
若祖孙三代的关系是折线（cur、parent、grandfather这三个结点为一条折线），则我们需要先进行双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。
抽象图表示如下：
另一种情况：当折线关系为，parent是grandfather的右孩子，cur是parent的左孩子时，就需要先进行右左双旋操作，再进行颜色调整。
分析完情况三，我们可以把情况三和情况二写在一起：在三种情况分类下，红黑树调整后，需要将根结点的颜色变为黑色，下一句return true;因为红黑树的根结点可能在情况一的调整过程中被变成了红色。
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（下）：https://developer.aliyun.com/article/1522290?spm=a2c6h.13148508.setting.19.50c04f0edmwqiI
