AVL树用平衡因子让树达到高度平衡
红黑树可以认为是AVL树的改良
通过给每个节点标记颜色让树接近平衡
以减少树在插入节点的旋转
在每个结点新增一个存储位表示结点颜色
可以是Red或Black
通过对任何一条从根到叶子的路径上各个结点着色方式的限制
红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
1.2 红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为啥满足上面性质的红黑树就能保证其最长路径节点个数不会超过最短路径节点个数的两倍？
由性质3可得出不能出现连续红色节点
由性质4可得出每条路径有相同黑色节点数量
极限情况下 最短路径：全黑 最长路径：一黑一红
由此可得出：最长路径不会超过最短路径的两倍
1.3 为什么更常用红黑树而不是AVL树？AVL树： 是一颗高度平衡的二叉树
查找效率：O ( l o g N )
但是这样的效率是在插入元素时经常性的旋转换来的
红黑树： 是一颗接近平衡的二叉树
假设全部黑节点有N个
整棵树的节点数量：[N, 2N]之间
最短路径长度：O ( l o g N )
最长路径长度：O ( 2 l o g N )
查找效率：O ( 2 l o g N )
10亿数据AVL树最多查找30次，红黑树最多也就查找60次，对于cpu的运行速度来说几乎可以忽略不计，但红黑树的规则相对于AVL树没那么严格，在插入元素时，不会经常旋转，所以综合而言红黑树更胜一筹
如图：对于AVL树必定旋转，红黑树则不用
二、红黑树模拟实现的基本框架2.1 红黑树节点的定义跟AVL树一样，只是AVL树采用平衡因子，让树达到平衡，而红黑树对节点进行颜色标记，让树达到平衡
定义一个枚举表示节点颜色
enum colour{ RED, BLACK,};template <class K, 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) {}};template <class K, V>class RBTree{ typedef RBTreeNode<K, V> Node;public:private: Node* _root = nullptr;};2.2 红黑树的插入还是和AVL树一样
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; 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; } } // 链接 cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } // new的节点的parent还指向空 cur->_parent = parent; // 插入黑色节点还是红色节点？ return true; }插入走到这里如果是AVL树，此时需要更新平衡因子
红黑树采用的是标记节点颜色，让树达到平衡，需要考虑的是插入什么颜色的节点？
插入黑色节点，会违反规则4，影响到每条路径插入红色节点，如果插入节点的父节点也是红色节点，则会违反规则3影响当前局部节点很明显插入红色节点更划算，所有插入的节点都默认是红色，如果违反红黑树的规则，再进行调整
相关视频推荐
需要C/C++ Linux服务器架构师学习资料加qun579733396获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享
三、对插入节点调整的解析如果插入节点的父节点为黑，则无需处理
如果为红，则分为三种情况
情况一：cur为红，p为红，g为黑，u存在且为红
cur为当前节点，p为父节点 g为祖父节点，u为叔叔节点
把p和u变黑，g变红
如果grandfather的parent也为红，把grandfather改为cur，继续按刚才的步骤往后迭代
如果grandfather为根节点，把grandfather改为黑色，颜色调整结束
情况二：cur为红，p为红，g为黑，u不存在或u存在且为黑
此树可能是完整树也可能是子树，u节点不存在
p为g的左孩子，cur为p的左孩子，则进行右单旋转
相反
p为g的右孩子，cur为p的右孩子，则进行左单旋转，p、g变色–p变黑，g变红
下图则是u节点存在的情况
c为下面4种情况的
任意一种包含一个黑节点的红黑树，d和e可能是空或者一个红节点
插入新节点，更新完后，继续往后更新，就是情况二的u存在的情况
情况三：cur为红，p为红，g为黑，u不存在或u存在且为黑
跟情况二完全类似，只是情况三为双旋，情况二是单旋
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转
相反
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2，此图为u不存在，u存在参考情况二
四、红黑树插入代码的全部实现详解都在代码注释
bool Insert(const pair<K, V>& kv){ if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; 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; } } // 链接 cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } // new的节点的parent还指向空 cur->_parent = parent; // 如果新插入节点破坏了红黑树规则 // 则更新节点颜色 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在或者u存在且为黑，旋转+处理 { // 如果插入节点在父节点的左，c、p、g呈一条斜线 // g // p u // c if (parent->_left == cur) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // 插入节点在父节点的右，c、p、g呈一条折线 // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; // parent->_col = RED; // 父亲本就是红，变一下双重保险 grandfather->_col = RED; } break; } } else // (grandfather->_right == parent) { Node* uncle = grandfather->_left; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在或者u存在且为黑，旋转+处理 { // g // u p // c if (parent->_right == cur) { RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; // 做个双保险，无论那种情况把根都变成黑的 return true;}五、红黑树全部代码模拟实现源码地址：https://gitee.com/black-9010/caddadd/blob/master/cpp_code/cpp_project/RBTree/RBTree.h