红黑树的创建、插入节点
一、红黑树的特性
(1) 每个节点或者是黑色，或者是红色
(2) 根节点是黑色
(3) 每个叶子节点是黑色（并且是空的结点）
(4) 不能出现两个连续的红色结点（如果一个节点是红色的，那么它的两个子节点都是黑色的）
(5) 从一个节点开始所有路径上包含相同数目的黑节点
关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。
二、红黑树的搜索
由于每一棵红黑树都是二叉搜索树，可以使用与搜索普通二又搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。
对普通二又搜索树进行搜索的时间复杂性为O(h)，对于红黑树则为O(log2n)。因为在搜索普通二又搜索树、AVL树( 平衡二叉搜索树，Self-balancing binary search tree)和红黑树时使用了相同的代码，并且在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下AVL树能获得最优的时间复杂性。
三、红黑树的插入操作
A、以二叉排序树的方式插入结点
红黑树首先是一棵二叉排序树，所以它的插入操作要遵循二叉排序树的插入原则。这个网址能模拟红黑树结点的插入过程： https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
B、待插入的节点应涂上红色
这样插入结点只可能破坏红黑树的两个性质：
(2) 根节点是黑色。
(4) 不能出现两个连续的红色结点
C、如何调整插入节点后带来的影响？
-
如果插入的结点是根结点，或者由于旋转、变色等原因，导致根结点变换，也需要将根结点设置成黑色。
-
如果（被插入结点N的）父结点P是黑色，则不需要做任何变化，从一个节点开始所有路径上包含相同数目的黑节点。
-
如果父结点是红色，则祖父结点G一定是黑色（不可能出现两个连续的红色结点）。插入的N结点是红色，需要重新平衡（将结点旋转、变色），又分为以下几种情况：
情况1：叔叔结点U（父结点的兄弟结点）是红色，则交换结点G和它的子结点的颜色。G变成红色，P和U变成黑色。
调整前： 调整后：
情况2：如果叔叔结点U是黑色，此时又有两种情况。
（1）N是P的左子结点，P是G的左子结点。**
在这种情况下只要对P做一次右单旋转，交换P和G的颜色，就可恢复红黑树的特性，并结束重新平衡过程。
调整前：
旋转后：
交换P与G的颜色：
（2）N是N的右子结点，P是G的左子结点。在这种情况下对P做先左后右的双旋转，再交换N与G的颜色，就可恢复红黑树的特性，结束重新平衡过程。
调整前：
先将P左旋转：
再右旋转，交换N与G的颜色：
（3）当结点P是G的右子结点的情形与P是G的左子结点的情形是镜像的，只要左右指针互换即可。
(A)
调整后：
(B)
调整后：