想要了解红黑树，首先你得了解二叉查找树（二叉排序树），了解左旋、右旋，你才能看懂这篇文章。

推荐文章：二叉平衡树（AVL树）从演变、平衡、旋转加练习题逐步分析，看不会过来打我

在前一篇文章也讲过，AVL平衡树的演变，其实红黑树也一样，它也是基于二叉搜索树实现的，可能你会问，不是已经演变出AVL树了吗？为什么还要有红黑树？

原因是这样的，AVL树追求的是极致平衡，当你插入一个元素时，旋转的次数不能预估，当插入、删除特别频繁时，树就会不停地旋转，严重影响效率，这时候红黑树出现了，红黑树能保证树的大致平衡，最多旋转3次就能实现平衡，它的查找时间复杂度为O(logn)。

每次新插入的数据一定是红色，如果插入的数据一旦是黑色，那么树就失去平衡了，因为整个树的节点都是黑色的，满足红黑树的所有特点，也就没有变色或旋转可言，所以每次新插入的数据一定是红色的，当打破红黑树的规则时，就会发生变色或旋转。

当前节点13为左子节点，父节点14为左子节点，这种情况先变色再旋转

第一步，变色，父节点变为黑色，爷爷节点变为红色

第二步，右旋（由/型变为^型）

先变为RR，右旋

根据RR，变色，左旋

例1

当前节点0038的父节点是红色且当前节点的叔叔节点0041也是红色，满足变颜色的条件：

例2

当前节点45，它的父节点40是红色，但是它的叔叔节点80是黑色，并且当前节点是LR，先变为LL，再变色旋转。

上面这张图节点40和节点45相连，且都是红色，根据红黑树的规则需要变色或旋转，节点40的父节点45是红色，它的叔叔节点80是黑色，且当前节点为LL，变色并右旋。

当前节点的父节点变为黑色

爷爷节点变为红色

爷爷节点以父节点为轴，右旋

遇到不满足红黑树条件的时候，首先判断当前节点的父节点和叔叔节点是否都为红色，如果都为红色，直接变色（父节点和叔叔节点变为黑色，爷爷节点变为红色），然后以爷爷节点为当前节点继续判断。如果当前节点没有叔叔节点或叔叔节点为黑色，那么判断当前节点是LL、LR、RR、RL，如果是LL或RR，则直接变色（父亲节点变为黑色，爷爷节点变为红色）并右旋或左旋。如果是LR或RL，则先把它们通过右旋或左旋变换为LL或RR，再进行变色旋转操作。

依次插入12，14，15，16，17，18，19，20，1，11，画出最终红黑树。

插入12

再插入14

再插入15

判断当前节点的叔叔节点是否为红色，叔叔节点不是红色，则判断该树为RR，需要变色并左旋

再插入16

不满足红黑树规则，先判断父亲节点和叔叔节点是否都为红色，都为红色，变色（父亲节点和叔叔节点都变为黑色，爷爷节点变为红色，根节点除外）

再插入17

RR，先变色再左旋

再插入18

再插入19

再插入20

变色后发现依然不满足红黑树规则，判断当前节点18父节点16是红色，叔叔节点12为黑色，这时候不需要变色操作，再看当前树为RR，所以需要先变色再左旋

再插入1

再插入11

完整流程如下图：