红黑树插入算法

红黑树节点插入与二叉搜索树类似，由根节点开始寻找待插入的位置。与二叉搜索树不同的内容大致有如下几点：

1、红黑树中所有新的节点，默认都是红色。
2、红黑树所有节点都需要记录父节点。
3、红黑树与二叉搜索树插入不同的是在节点插入之后要进行规则校验
4、如果红黑树不平衡，就要进行修复动作：
4.1、如果插入的是根节点，那么违反红黑树根节点必须为黑色规则，就直接把节点修改为黑色；
*4.2、如果插入节点的父节点是黑色的，则符合红黑树规则，跳过此步骤；
*4.3、如果插入节点的父节点是红色的，祖父结点的另一个子节点是红色，则将祖父节点变红，而父和叔节点变黑，然后设置祖父节点为当前节点，然后重新开始判断；
*4.4、如果插入节点的父节点是红色的，祖父结点的另一个子节点是黑色，则分几种情况讨论：

1、插入节点是其父的左子节点，而父节点是祖父节点的左子节点，那么：把父节点变为黑色，祖父节点变为红色，然后对祖父节点进行右旋，然后重新开始判断
2、插入节点是其父的右子节点，而父节点是祖父节点的右子节点，那么：把父节点变为黑色，祖父节点变为红色，然后对祖父节点进行左旋，然后重新开始判断
3、插入节点是其父的右子节点，而父节点是祖父节点的左子节点，那么：把当前节点的父节点做为新的当前节点，对新的当前节点进行左旋，然后重新开始判断。
4、插入节点是其父的左子节点，而父节点是祖父节点的右子节点，那么：把当前节点的父节点做为新的当前节点，对新的当前节点进行右旋，然后重新开始判断。