继搜索二叉树和AVL树后有了红黑树。
AVL树改善了搜索二叉树在极端情况下的严重效率退化，但是在运用得过程中发现他对平衡的要求几乎达到了苛刻的地步，往往经过一系列复杂的变化只是将树的深度优化了一点点，而这一点点在现在日益快速的处理器下根本不起眼，于是有了更优的结构红黑树：
红黑树有以下几条规则：
1：根节点是黑色。
2：叶子节点是黑色。
3：若一个节点是红色则此结点的子树根节点一定是黑色。
4：任意节点开始到每个叶子节点的简单路径中黑的的节点数相同。
就是上面几条规则使这个数的平衡得到了保障，使之成为了比较优选的储存结构；
分析：每条简单路径的黑结点数相同使其每个子树允许的最大高度差变成了二倍，这样减少了旋转的次数，也没有将树查找的时间复杂度变得很慢，而最段路径都是黑色，和最长路径红黑交叉深度不过是差了一倍，也就是说时间复杂度只是比AVL数多了一倍罢了，对于飞快地处理器，这点增加无伤大雅。
树的结点比起AVL数和普通二叉搜索树，略有不同：
只多了一个记录颜色的节点：
插入函数：
1：先判断树为空的情况，若为空插入后将节点变为黑色，需要满足上述第一条规则，若不为空先找到需要插入的位置，因为底层是搜索二叉树所以不能有相同的键，当相等时插入失败，若不相等则根据大小将cur插入到合适的位置。
插入的结点应该默认为红色，插入红色不违反每条路径黑色结点数量相同的规则，因为若为黑色则会使这一条路径与其他路径不一样而导致很麻烦，插入红色后进行判断若其双亲结点为黑色，则不违反任何规则，插入结束，若双亲结点为红色就需要调整，但是调整又会影响其他结点又变为红色，所以出现下图着一种情况时，不能判断cur是否为新插入还是由于颜色变化导致cur是由黑色变为红色，
若出现前者则需要变为后者，但是后者的根节点变成了红色若后者时另外一棵树的子树那么就需要继续向上发生这样的调整。这是红黑树第一种需要调整的情况。
代码思路：设置一个while循环当parent不为空且cur的颜色与parent的颜色相同时调整parent与其兄弟结点的颜色，并改变根节点的颜色。
第二种情况：
如上图cur因为第一种情况变色后与parent颜色一样，违反了上述第三条规则，但此时若还是仿照第一种情况只用变色来处理，发现处理不了，所以只能用旋转和变色一起处理，
对最上面的grandfather结点进行右旋变成了图二，在对图二进行变色变成图三。当然除了cur和parent在左边的情况也有在右边的情况，只是旋转方向不一样罢了。
第三种和情况：
上图中cur在parent的右边，此时又是另外一种情况，这种情况与前两种都有所不同，但是发现对parent进行左旋就会变成第二种情况，那么问题就迎刃而解了，当然第三种情况也有parent和cur在右边的情况，只是旋转方向不一样罢了，需要注意的是，当第一次旋转后虽然与第二种情况相似，但也不能完全用第二种方式处理，因为parent和cur的位置不一样。需要处理交换一下位置才能完全转化为第二种情况。最终都是将每条路径中的黑色结点数目处理成一样的。
如此这样就将红黑树所有的情况都考虑了。完了以后就要测试是否为红黑树了。
红黑树的测验需要卡每条规则是否成立：
1：写一个函数。先判断是否为空。若为空返回true因为空红黑树也是红黑树，再检测根节点是否为黑色，然后用while迭代一条路计算一台路的黑色结点数，
再写一个子递归函数，将根节点和计算到的黑的结点数count传入，先写结束部分，若递归函数为空则表示二叉树的一条路径跑完了，则判断这条路径的黑结树=数是否等于count，若等于返回true,然后是递归部分：判断此结点是否为黑色结点,若是黑色节点则结点数N++，再定义一个结点指针指向此结点的双亲结点，再判断两个结点是否都为红色，然后递归进入左子树和右子树。
测试结果为是红黑树。
这里贴上旋转函数，和中序遍历函数：
标签：24,黑树,结点,cur,parent,日红,插入,节点 From： https://www.cnblogs.com/qjwxlj/p/17354191.html