红黑树
1、什么是红黑树
红黑树是一种不严格的平衡二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。
红黑树特性如下：
- 根节点是黑色
- 每个节点要么是黑色要么是红色
- 每个红色节点的两个子节点一定都是黑色
- 每个叶子节点（NIL）都是黑色
- 任意一个节点的路径到叶子节点所包含的黑色节点的数量是相同的---这个也称之为黑色完美平衡
- 新插入的节点必须是红色->为什么？如果新插入的节点是黑色，那不管是在插入到那里，一定会破坏黑色完美平衡的，因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了。
2、为什么需要红黑树？
- 对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O(logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。
- 那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。
- 红黑树的查询性能略微逊色于二叉平衡树, 但是红黑树在插入和删除上优于二叉平衡树 ； 总体来讲，红黑树的插入、删除、查找各种操作性能都比较稳定，对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。
3、红黑树如何维持平衡？
红黑树通过，左旋，右旋，变色来维持平衡：
- 左旋：以某个节点作为固定支撑点（围绕该节点旋转）,其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变；
- 右旋：以某个节点作为固定支撑点（围绕该节点旋转），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变；
- 变色：节点的颜色由红色变成黑色，或者是由黑色变成红色。
左旋和右旋：
染色：
