二叉树我们都知道，就是一棵树，红黑二叉树是满足特殊条件的二叉树，这棵树是一颗有颜色，而且符合一定规则的树，规则如下：

• 根节点必须是黑色的
• 没有两个红色节点是紧挨着（父节点和子节点不可以同时为红色）
• 从根节点到任意末尾节点的黑色节点必须是相同的

如下图所示的三棵树：

 

树1： 满足根节点是黑色的，也没有两个红色节点相连，但是不满足最后一个条件

树2：满足所有条件

树3：不满足第三个条件

注意：我们认为默认的节点都有两个值为None的两个节点

红黑二叉树的插入

我们现在看一下如何将一个元素插入红黑二叉树：

• 如果是一个None的树，我们直接创建一个根节点，并且颜色为黑色
• 所有插入的新的节点，颜色都是红色的
• 如果插入节点后，插入节点的父节点是黑色，完成插入
• 如果插入节点后，插入的节点的父节点红色 ，则分两种情况：

1:如果这个红色父节点没有同级的兄弟姐妹，或者兄弟是黑色：调整颜色即可

2:如果这个红色节点的兄弟是红色，修改颜色兄弟和自己的颜色，并且修改父节点的颜色（如果父节点不是根节点的话）

 

例子如下：

下面就是特殊情况了：当我们插入完成之后，如果出现 “红-红”如何解决：

第一种情况：插入元素为红，父节点为红，父节点的兄弟节点为红的时候：修改父节点和其兄弟节点的颜色，并将父节点的父节点修改颜色（除非是根节点）

注：点击查看大图

 

 

情况2：若果插入之后出现“红-红”，并且插入节点为左节点，父节点为左节点的情况下，父节点的兄弟节点不存在的情况：右旋转，具体步骤点击查看大图

 

情况3：若果插入之后出现“红-红”，并且插入节点为右节点，父节点为左节点的情况下，父节点的兄弟节点不存在的情况：先左旋转，然后右旋转，具体步骤点击查看大图

演示一个复杂的的情况4：

 

其实，我们都遵循如下规律：

• LL ——>R
• RL—->LR
• RR——>L
• LR——->RL

解释一下： 前边是我们遇到红红的情况，第一个L，是指父节点是左节点还是右节点，第二个是指插入节点是做节点还是有节点，然后根据这两个进行后边旋转的选择，例如情况1就是 LL 所以我们只需要一次右旋转即可，此处要注意，我们旋转后的颜色变化，右旋转后，父节点和爷爷节点的颜色发生变化了，左旋转病没有变化