目录
一、红黑树的概念
二、怎么做到最长路径与最短路径相差小于等于两倍? （性质）
三 、极端场景分析最长路径和最短路径：
四、AVL树和红黑树的效率对比：
五、树的路径包括叶子结点的空结点
六、红黑树的插入结点时的相关规则：
（一）、插入结点的颜色必须为红色
（二）、处理规则：
1、情况一：uncle结点存在且为红：
对于情况1我们可以分析一下不同种类的树的个数：
（1）、a，b，c，d，e都是空树，cur是新增：
（2）、c，d，e是具有一个黑色节点的红黑树（子树）
（3）、c,d,e,是每条路径上有2个黑色结点的红黑子树
（4）总结：
总体抽象图如下：便于分析不同情况时进行对应更改
2、情况二：uncle不存在或者uncle存在且为黑色：（旋转+变色）
（1）、单旋规则：
（2）、双旋规则：
（3）、uncle不存在
举例单旋：
（4）、uncle存在且为黑色
举例单旋：
举例双旋：
七、红黑色底层模拟实现：
2. 红黑树类定义
3. 辅助函数实现
3.1 获取祖父节点函数
3.2 获取叔叔节点函数
3.3 左旋操作函数
3.4 右旋操作函数
4. 插入操作及插入后调整函数
4.1 插入函数
4.2 插入后调整函数
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家
点击跳转到网站
前面还有AVL树的知识。
问题1：为什么满足性质就可以使高度得到满足；
问题2：为什么AVL树高度接近logN，红黑树高度接近2logN
一、红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 
二、怎么做到最长路径与最短路径相差小于等于两倍? （性质）
只需满足以下几个性质：
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的 （ 即没有连续红色的结点 ） 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 （ 保证每条路径上的黑色结点个数都相等）。 5.规定每个叶子结点的两个空孩子都是黑色的，通常称为： NIL ，所以说红色结点可以作为叶子结点。
三 、极端场景分析最长路径和最短路径：
最短路径：全是黑色结点； 最长路径：两个黑色结点中夹一个红色结点； 解释：假设每条路径有四个黑色结点，因为规定每条路径的上的黑色结点个数必须相同， 所以最短的情况就是只有这四个黑色结点，即最短路径长度为：4；最长路径就是每两个黑色结点之间还有一个红色结点，并且因为规定了NIL结点是黑色结点，所以红色结点可以作为叶子结点，所以最长路径为：8。
但要注意，这只是极端情况存在，不是每一颗红黑树都存在这样的最短和最长路径。 四、AVL树和红黑树的效率对比：
AVL树的高度是很接近logN的 红黑树的高度是很接近2*logN的 所以可以说红黑树的效率是相对ALV树来说要差一些。 但这个 差距几乎可以忽略不计，所以logN是足够小的（例如当N = 10亿， logN = 30，对与红黑树也就是2 * logN = 60）,而 内存CPU通常一秒就能进行上亿次循环，所以说这个差距是可以忽略的。 同时，插入同样的数据，AVl树高度更低是通过更多的旋转的达到的。五、树的路径包括叶子结点的空结点
要注意树的高度的概念，是包括叶子结点的空结点的。 也就是说，如下：
因为路径包含了叶子结点的空结点，所以我们数路径数就数NIL节点的个数，即路径数为：11 六、红黑树的插入结点时的相关规则：
红黑树插入结点后的处理讨论情况思维导图
（一）、插入结点的颜色必须为红色
也就是说，插入结点时的颜色必须为红色，原因如下： （1）、若插入结点的颜色为黑色，那么该路径上的黑色结点就会比其他结点多一个，而我们无法控制其他路径，这样就必定会违反红黑树的规则； （2）、若插入结点的颜色为红色：又分为两条规则： 若插入位置的父亲是黑色，则不需要处理，插入结束； 若插入位置的父亲是红色，此时就出现了连续的红色结点， 需要进行处理 ；（二）、处理规则：
利用一个抽象图进行分析：
（在AVL树中的抽象图中a,b,c,d,e是代表一颗子树的形状，而红黑树中这里代表有几颗红色或黑色结点的红黑树子树。）
解释：
cur指当前的插入结点cur；
p为父亲结点parent；
g为爷爷结点grandfather；
u为叔叔uncle;
因为规定了插入结点cur为红色，所以我们可以知道cur、p、g是确定的，所以我们关键要看uncle的颜色，根据uncle结点的颜色进行分析不同情况：
1、情况一：uncle结点存在且为红：
规则：
<-：p和u结点变黑；
<-：g结点变红；
<-：如果g结点是根结点，再把g结点变黑（因为规则规定根结点必须为黑色，而根节点是每条路径的开始，所以根节点变黑，相当于每条路径的黑色结点都增加了一个，所以数量还是相等的。）
<-：如果g结点不是根，则继续往上迭代处理（往上更新c、p、g、u结点，继续判断，直到c的父亲为黑或者为根结点）。
注意：p、u是g的左节点还是右结点都不影响，cur是p的左孩子还是右孩子也不影响，处理方式都是一样的。
对于情况1我们可以分析一下不同种类的树的个数：
（1）、a，b，c，d，e都是空树，cur是新增：
处理过程：
（2）、c，d，e是具有一个黑色节点的红黑树（子树）
因为c,d,e路径上都有一个黑色结点，所以cur原本也是黑结点，这样才能保持黑色结点个数相同，所以新增结点会在cur下面，后面因为下面插入新节点，就导致cur变为红节点，然后继续处理。
具有一个黑色节点的红黑树有以下四种情况：
所以此时一共有256种情况（4*4*4*4）
但无论哪一种，处理方式都是一样的：
（3）、c,d,e,是每条路径上有2个黑色结点的红黑子树
（4）总结：
无论多少种，处理方法都是一样的，我们要抓大局。
通过上述，我们可以看到，红色结点都是插入的，黑色结点都是为了满足规则变出来的（增加黑色结点个数的清理为将根结点变成黑色，其他都是为了保持黑色结点数量相等）。
总体抽象图如下：便于分析不同情况时进行对应更改
2、情况二：uncle不存在或者uncle存在且为黑色：（旋转+变色）
（1）、单旋规则：
上述情况一只需要变色处理，所以不用关心左右结点；
现在情况二是需要旋转的，所以需要关心左右孩子，如下：
<-：若p为g的左孩子，cur为p的左孩子，则左边高，进行右单旋转；
<-：若p为g的右孩子，cur为p的右孩子，则又边高，进行左单旋转；
<-：同时p变为黑色，g变为红色；
（2）、双旋规则：
<-：若p为g的左孩子，cur为p的右孩子：左右双旋+变色；
<-：若p为g的右孩子，cur为p的左孩子：左右双旋+变色；
<-：因为双旋就是两次单旋，所以进行一次旋转就变色，变色规则与单旋相同。
（3）、uncle不存在
举例单旋：
抽象图如下：p为g的左孩子，cur为p的左孩子，则左边高，进行右单旋转；
因为uncle不存在，所以每条路径都只有一个黑，所以c,d,e,f位置都为空，cur为新增结点。
此时不能通过变色处理，所以只能通过旋转+变色方式处理，如下：
旋转规则和AVL树相同：
举例双旋：
（4）、uncle存在且为黑色
举例单旋：
因为uncle为黑色，所以每天路径至少有两个黑色结点，所以c位置为黑色，cur位置为黑色，cur不再是新增结点，cur的孩子a,b位置为红色，新增结点为a或b的任意一个孩子处。
新增前我们可以看到此时就是极端情况，最长路径是最短路径的两倍，若此时在a，b的孩子处插入结点，就会违反高度规则，此时就会进行旋转操作：
原貌如下：
最下面新增节点属于情况一，然后进行变色处理，导致cur变红色，然后发现出现了连续的红色结点，所以需要进行处理；因为uncle为黑色，所以就不能像情况一那样进行变色处理，此时又违反高度规则，所以就进行旋转操作，规则与AVL树相同。
举例双旋：
七、红黑色底层模拟实现：
#pragma once#include<iostream>using namespace std;//红黑树，不是红就是黑，枚举enum Color{RED,BLACK};//红黑树结点类，<K，V>模型//struct默认访问权限为公有template<class K,class V>struct RBTreeNode{//三路RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//<K,V>模型用pair对象pair<K, V> _kv;//枚举颜色Color _col;RBTreeNode(const pair<K, V>& kv ):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//插入结点为红色{}};//红黑树结构类template<class K,class V>class RBTree{typedef RBTreeNode<K, V> Node;public://插入bool insert(const pair<K, V>& kv){//第一次插入,单独判断根节点if (_root == NULL){_root = new Node(kv);_root->_col = BLACK;return true;}//正常插入Node* parent = nullptr;Node* cur = _root;//找到空位置//cur小于kv，cur向右走变大//cur大于kv，cur向左走变小//直到cur为空代表找到插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{//插入失败return false;}}//找到插入位置后，new出结点cur = new Node(kv);//判断cur是左孩子还是右孩子if (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入成功之后，检查是否违反红黑树规则,违法就处理//父亲不存在，则只有根节点，插入结束；//父亲存在且为黑，不违反规则，插入结束；//父亲存在且为红，则进行分类处理；while (parent && parent->_col == RED){//记录爷爷,爷爷一定存在，解释如下：//若爷爷为空，则代表父亲是根节点，说明父亲为黑，不会进入此循环Node* grandfather = parent->_parent;//先处理父亲是爷爷左孩子的情况：//因为涉及旋转，所以需要区分左孩子和右孩子if (grandfather->_left == parent){//则叔叔为爷爷的右孩子Node* uncle = grandfather->_right;//情况一：叔叔存在且为红，进行变色处理：if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新判断cur = grandfather;parent = cur->_parent;}else{//情况二：叔叔不存在或者叔叔为黑色//因为父亲在爷爷的左;//所以若孩子为父亲的左，则进行右旋转+变色（下来的变红，上去的变黑）// g// p (u)// curif (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//孩子为父亲的右，进行左右双旋// g// p (u)// curRotateL(parent);// g// cur (u)// pRotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}//因为旋转后的变色处理为：上去的变黑，下来的变红//所以旋转过后该子树的根是为黑的，所以与上面的结点是不会违反规则的（不会出现连续的红色结点）//所以到这里插入就结束了，不需要再进行判断，直接break结束；break;}}else{//这里讨论父亲是爷爷的右孩子的情况//则叔叔是爷爷的左孩子：Node* uncle = grandfather->_left;//情况一：叔叔存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = BLACK;//向上更新cur = grandfather;parent = cur->_parent;}else{//情况二：叔叔不存在或者叔叔存在且为黑//若孩子为父亲的右，则进行左单旋+变色：// g// (u) p// curif (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// （u） p// cur//若孩子为父亲的左，则进行右左单旋+变色RotateR(parent);RotateL(grandfather);cur->_col = BLACK;parent->_col = grandfather->_col = RED;}break;}}}//插入完成后暴力处理将根节点置为黑色_root->_col = BLACK;return true;}//左单旋void RotateL(Node* parent){//重新链接结点Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;//与上面进行链接：Node* ppnode = parent->_parent;parent->_parent = subR;//ppnode为空，说明parent是根结点，则旋转后将subR作为根结点if (parent == _root){_root = subR;subR->_parent = nullptr;}else{//parent的父亲不为空,就判断parent是父亲的左孩子还是右孩子if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left = parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}//中序遍历，为了方便递归，所以会套一层子函数void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first<<" ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);}private:Node* _root = nullptr;};#include"_RBTreeNode.h"int main(){//HF::RBTreeNode<int,int> node(make_pair(1,1));int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> tree;for (auto e : a){tree.insert(make_pair(e, e));}tree.InOrder();return 0;}