红黑树的插入

推荐一个学习红黑树的工具网址，可以动态生成红黑树，一步一步观察插入和删除的步骤。
红黑树动态生成网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

1.红黑树的5大特性

节点要么红色要么黑色
根节点一定是黑色
红色节点的子节点一定是黑色（NULL节点看成黑色）
没有连续的两个红色节点（但可以有连续的黑色节点）
从任何一个节点出发到NULL叶子节点的路径包含的黑色节点数量相同（红黑树的叶子节点定义跟往常的不一样，指的NULL节点）

2.与二叉查找树的关系

红黑树首先是一个自平衡的二叉查找树，但是它不是绝对平衡。它能保证整棵树从根节点出发到所有叶子节点的最长路径不超过最短路径的两倍，是相对平衡，单次搜索的时间复杂度为O(2lgN)，N为节点数目（不包含NULL叶子节点）。

红黑树也具有二叉查找树的特性：

任意节点的值，都比它左子树中所有的值大
任意节点的值，都比它右子树中所有的值小
任意节点的左右子树也必须是二叉查找树

但是二叉查找树会有一些极端情况，形成单边树，搜索查找效率降为O(N)。红黑树就是通过自平衡的方式解决这种不平衡的问题，自平衡的操作包括变色和自旋。红黑树的插入

3.红黑树的插入

3.1 插入

红黑树插入节点符合二叉查找树的节点插入规则。
假如有待插入节点I，首先从根节点开始遍历整棵树，待插入节点I的值比遍历到的节点值小的话，进一步搜索该节点的左子树，否则搜索该节点的右子树，直到找到某一节点P，根据值的大小关系进一步遍历时发现P对应的子节点为空，I就作为P的子节点插入。

3.2 平衡

但是红黑树插入节点后有后续操作。
红黑树待插入的节点I，默认是红色。由于插入新节点后有可能会违反红黑树的5大特性，我们需要使用变色和自旋的方式来调整树结构维持红黑树的5大特性。

3.2.1变色

变色操作很简单，就是简单地把节点在红色与黑色之间转换。某些插入后的平衡操作可能让同一个节点不止变色一次。见4.3.1插入的例子。

3.2.2自旋

自旋分为左旋和右旋，两者的操作是完全对称的，理解了其中一个就能理解另外一个。

3.2.2.1右旋

假如我们需要对下面这棵子树进行以0030为中心右旋的操作
红黑树的插入
我们现在不需关注颜色的变化，以0030为中心右旋操作之后得到下面的树结构。我们可以很形象地想象用手将0020节点提起来放在了0030节点的位置，而0030节点掉了下来。

以某节点N为中心右旋，大体直观地看就是让N的左子节点成为N的父节点，而N成为他原本左子节点的右子节点。到这里已经基本能理解右旋了。

细一点看还要考虑他们其他父子节点的关系变化。
假设N为自旋中心节点，P表示父节点 PP表示祖父节点 LC表示左子节点 RC表示右子节点
N的父节点变为N的左子节点的父节点
N.LC.P = N.P
N的父节点的左/右子节点变为N的左子节点（左还是右与N是其父节点的LC还是RC一致）
N.P.LC/RC = N.LC
N的左子节点的右子节点变为N
N.LC.RC = N
N的父节点变为N的左子节点
N.P = N.LC
N的左子节点的右子节点的父节点变为N
N.LC.RC.P = N
N的左子节点变为N的左子节点的右子节点
N.LC = N.LC.RC
(以上关系转变可用于编程实现，在遇到N.LC.RC的赋值时需要判断其是否为空）

3.2.2.2左旋

左旋的话就是相对右旋完全对称的操作。举一个左旋前后的例子应该就能马上看懂了，同样无需关注颜色的变化。
红黑树的插入
以0050为中心左旋得到以下树结构

4.节点插入时的情况分析

假定待插入节点为I，其父节点为P，祖父节点为PP，叔叔节点（祖父节点的另一个子节点）为U

4.1. 根节点为空

I=>0010

平衡方案：直接插入，I变为黑色（性质2）

红黑树的插入

4.2. 父节点P为黑色

I=>0005

平衡方案：不增加黑节点数量，无需平衡，直接插入
. 红黑树的插入

4.3. 父节点P为红色

由性质4知道，祖父节点PP肯定存在，且为黑色（后不再说明）。此时出现连续出现两个红色节点（I和P）的情况，违反了性质4，所以需要后续的平衡操作，且需要进一步细分情况讨论。
红黑树的插入

4.3.1. 叔叔节点U为红色

I=>0001

平衡方案：P和U都变为黑色，PP设为红色，然后把PP看成是插入节点I再进行平衡判断（因为有可能PP的父亲节点也是红色，所以又会违反性质4触发平衡操作）。
特例：如果最终平衡后的PP’（可能经过多次平衡，不再是刚开始的PP）是根节点则设为黑色（性质2）。
红黑树的插入
由于PP=>0010是根节点，所以要设为黑色