?红黑树转换：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
?红黑树的性质
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
插入情况? ? ? ? （不建议直接看插入情景，直接看下面例子）
? ? ? ? 1. 父结点为黑色时
? ? ? ? ? ? ? ? 直接将插入结点与父结点
? ? ? ? 2.父结点为红色时
? ? ? ? ? ? ? ? 2.1 若插入结点的父结点的兄弟结点为红色时，父结点和父结点的兄弟结点变为黑色，父结点的父结点变为红色，此时插入结点为父结点的父结点
? ? ? ? ? ? ? ? 2.2 若插入结点的父结点的兄弟结点为黑色时 （这种情况不存在）
? ? ? ? ? ? ? ? 2.3 若父结点是左结点且无兄弟结点时
? ? ? ? ? ? ? ? ? ? ? ? 2.3.1 插入结点插入到父结点的左结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋
? ? ? ? ? ? ? ? ? ? ? ? 2.3.2 插入结点插入到父结点的右结点时，先对父结点左旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋
? ? ? ? ? ? ? ? 2.4 若父结点是右结点且无兄弟结点时
? ? ? ? ? ? ? ? ? ? ? ? 2.4.1 插入结点插入到父结点的右结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋
? ? ? ? ? ? ? ? ? ? ? ? 2.4.2 插入结点插入到父结点的左结点时，先对父结点右旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋
下面我们用例子来说明（下面讨论都不引入”叶子是NIL结点“，图1不含有NIL结点，图2含有NIL结点）
??????????????????????????????图 1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图 2? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?向下图中的图1 插入一个250的结点（插入的结点都是红结点）
?
?变化过程如下图(变化情景应为 2.1)
?? ? ? ? ? ? ? ? 2.1 若插入结点的父结点的兄弟结点为红色时，父结点和父结点的兄弟结点变为黑色，父结点的父结点变为红色，此时插入结点为父结点的父结点
?
?
?
?对下图 插入一个 100 结点 变化过程 如下图
?? 2.3.1 插入结点插入到父结点的左结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋
?
?对下图 插入一个 270 结点 变化过程 如下图
?? 2.3.2 插入结点插入到父结点的右结点时，先对父结点左旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋
?
?
?向下图插入一个450的结点
2.4.1 插入结点插入到父结点的右结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋
?
?
??向下图插入一个370的结点
?? 2.4.2 插入结点插入到父结点的左结点时，先对父结点右旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋
?
?
?
?
?
?
????????