红黑树-01 红黑树原理和特性，插入结点变色调整原理与插入结点实战
红黑树-01 红黑树原理和特性，插入结点变色调整原理与插入结点实战
一、红黑树原理
红黑树也是一种自平衡二叉树（AVL树），但是相对于AVL树，又添加了红黑两种颜色区分结点，导致红黑树有了基于颜色的约束，红黑树需同时满足下面四个约束：
1，必须是二叉树。即：必须符合 左<根<右 的规则；
2，根结点和叶子结点必须是黑色。其中：叶子结点指的是空结点。比如：一个普通的AVL树，假如只有三个结点：【结点1】，【结点2】，【结点3】，在AVL树中，三个结点已构成AVL树，但是在红黑树中，每个叶子结点都有隐藏的空结点，如下图一。
3，每个红色结点的两个子结点都是黑色。即：不能存在连续的两个红色结点；
4，从任一结点到其每个叶子结点的所有路径都包含相同数目的黑色结点。即：随意选择树上的一个结点，从该结点通往其叶子结点（即空结点），每条路径中的黑色结点个数相同（包含空结点）。如下图二，根结点【结点2】到所有叶子结点的黑色结点数量都是三个。
图一
图二
上述红黑树的四个核心约束，有个便于记忆的口诀，分别对应上述的1234：
左根右、根叶黑、不红红、黑路同
二、红黑树特性
最长路径不超过最短路径的两倍
以上图二为例，最长路径必定是黑红交替的路径（取决于约束3），总长度=5；最短路径必定全是黑色结点（取决于约束4），总长度=3
红黑树与AVL树比较
查询：因为AVL树的特性是左右子树的高度差小于等于1，而红黑树的左右子树高度差可以大于1，即AVL树相较于红黑树更加平衡，所以在查询方面，AVL树比红黑树效率更高；
增删：AVL树为保证更高的平衡度，导致其在增删结点时要做的旋转操作更多，所以在增删方面，红黑树效率更高。
三、红黑树插入/增加结点
插入结点默认是红色
因为如果插入的是黑色结点，必然违反【黑路同】的约束。相反，如果插入节点是红色结点，可能并不违反任何约束，不需要做调整。如果在刚插入的结点上再插入一个结点，则违反了【不红红】的约束，需要调整。另外，如果插入的结点是整个树的第一个结点，即根结点，则违反了【根叶黑】的约束，也需要调整。具体调整方案，下文直接以案例形式讲解。
1，插入根结点
插入根结点时，违反了【根叶黑】的约束，调整方式直接将根结点变黑即可。
2， 插入非根结点
插入非根结点时，需要根据插入结点的叔叔结点的颜色，做不同的调整。叔叔结点是指：与插入结点的父结点同级的结点，如果为空，则叔叔结点就是黑色的空结点。
2.1，叔叔结点是红色
违反约束：【不红红】
调整方式：
1，爷爷层结点和叔父层结点颜色互换；
2，将爷爷结点当成新增结点，再根据红黑树的四大约束进行调整。
2.2，叔叔结点是黑色
违反约束：【不红红】
调整方式：
1，先去掉空结点，再以AVL树的平衡规则判断失衡结点和失衡类型：LL型、LR型、RL型、RR型。上图可知，失衡节点为：【结点2】，失衡类型为：RR型，调整方式为：【结点2】左旋。AVL树失衡类型及旋转方式详见：https://blog.csdn.net/aquriushu/article/details/144831151
2，对【旋转点】（即失衡结点）和【旋转中心点】变色：黑变红、红变黑。
再举一个例子，当失衡类型为LR型或RL型时，如何调整呢，如下图：
四、案例
前文已将红黑树的插入原理分析完成，下面以一个稍微复杂的案例讲述插入过程。
插入结点：17、18、23、34、27、15、9、6、8、5、25。
1，插入【结点17】，如下图：
2，插入【结点18】，如下图：
3，插入【结点23】，如下图：
4，插入【结点34】，如下图：
5，插入【结点27】，如下图：
6，插入【结点15】，如下图：
7，插入【结点9】，如下图：
8，插入【结点6】，如下图：
9，插入【结点8】，如下图：
10，插入【结点5】，如下图：
11，插入【结点25】，如下图：