数据结构-红黑树
RB-tree:红黑树利用非严格的平衡，牺牲了一定的查找效率，但更大程度上增加了插入删除的效率。从功能，性能，空间开销等方面来综合考量，红黑树的综合表现来讲胜于AVL树。
应用：在JDK集合类TreeMap和TreeSet底层就是红黑树实现的，在JAVA8中，连HashMap也用到了红黑树。
为什么是红黑树
- 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
- 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
- map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。
红黑树的规则
- 根节点是黑色
- 叶子节点都是黑色空节点（NIL节点）。
- 节点是红色或黑色。
- 红色节点都有两个黑色的子节点。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树的操作
参考链接中的维基百科-红黑树，对此有非常详细的描述。
插入：每一个新插入的节点都标为红色（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换和旋转来调整。）
删除：RB_TREE是二叉平衡树，在二叉查找树中，删除一个带有两个子节点的节点时，是将左子树中的最大元素或右子树中的最小元素节点删除，然后将其节点值放入当前节点。RB_TREE也是如此，因此删除带有两个子节点的操作就被简化为了删除只有一个子节点的节点的操作。
在只有一个儿子的节点中。如果他是红色，他的父亲和儿子节点必然都是黑色，因此只需要简单的将儿子节点替换到他的位置即可。如果他是黑色，而且他的子节点是红色，如果简单的删除该节点会导致，不符合RB_TREE的定义。只需要将儿子涂黑再替代即可。