一、如何定义一棵"红黑树"？
顾名思义，红黑树中的节点，一类被标记为黑色，一类标记为红色。除此之外，一课红黑树还需要满足这样几个要求：
1.根节点是黑色的；
2.每个叶子节点都是黑色的的空节点（NIL)，也就是说，叶子节点不存储数据；
3.作保相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4.每个节点，从该节点到达其可达叶子节点的所有路径，都包含数目相同的黑色节点；
二、红黑树与AVL树相比有什么优势？
AVL树是一种高度平衡的二叉树，所以查找效率非常高，但是，有利就有弊，AVL树为维持这种高度的平衡，就要付出更多的代价。每插入删除就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
红黑树也是一种平衡二叉查找树。红黑树只是做到了近似平衡，但不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。所以，红黑树的插入、删除、查找各种操作性能都比较稳定。
三、实现红黑树的插入、删除需要平衡调整
当在插入、删除节点的过程中，红黑树的第三、第四点要求可能会被破坏，而“平衡调整”，实际上就是要把被破坏的第三、第四点恢复过来。
在平衡调整包含两种基础的操作：左右旋转和改变颜色
左旋（rotate left)：围绕某个节点的左旋；
右旋（rotate right)：围绕某个节点的右旋；
关于红黑树的调整，在网上有很多资料，其中红黑树很有关联的2-3-4树，这里有相关的解释，看了之后会有更深的理解：https://www.cnblogs.com/tiancai/p/9072813.html
不过网上有很多内容看不懂，特别是在插入、删除的节点的颜色标记 红黑、黑黑，红-黑黑... 让人难以理解。
下面写一个插入的案例，用图的方式以帮助理解；根据红黑树的4个要求来进行调整，这样思路不会跑偏。
1、往红黑树中插入数据16，默认插入的颜色是红色，这里为什么是红色？如果为黑色，当你连续插入，会影响要求4；红色可以通过调整成为标准的红黑树；
2、如上图1右图，当我们插入16之后很明显就不符合要求3，这时我们我们可以看到把只要把9，12 跟11的颜色对换，就不会影响它们下面的节点了；
我们知道调整平衡可以用左右旋转和改变颜色，为什么要先改变颜色？因为改变颜色不会对树的结构造成变换，这样刚好这时有人在查询的时候跟之前一样! 所以我们建议先用改变颜色能不能解决，不能的话再用左右旋转。
3、如上图2左图，我们可以看到11，19都是红色，很明显不符合要求3；我们发现改变11或19的颜色都会不符合要求4，这时改变颜色没有用了，那就用旋转，我们把节点11右旋转，右旋转之后见图2右图，我们发现这时已经符合要求4了，但是11，19这两个节点不符合要求3，改变11，19的颜色也不符合要求4，我们再把11左旋转。这时看图2右图我们发现这个树已经变成极不平衡了；
红黑树有根节点黑色这一要求，所以我们在用旋转的时候只要把当前节点往上走总会有解决的时候。
4、如图4，我们把11节点旋转之后，发现只要改变8，11的颜色，就可以让整个插入的操作经过调整又变成红黑树了。
总结：经过上面插入的案例，我们发现通过改变颜色和左右旋转就可以完成对红黑树的调整，这只是一种情况的操作，我看有些资料关于红黑树的更新（插入和删除）有分好几种情况，分别要怎么去调整，其实都可以这样去总结出来的。
