红黑树

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

为啥要有红黑树？

二叉树的不平衡

由于二叉树可能会严重的不平衡，导致查找和插入基本成了线性的，所以出现了红黑树。

在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。

红黑树的调整

变色

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

旋转

左旋转

就是使得以X节点为轴做左旋转，X节点的右孩子Y成为它的父节点，Y的左孩子成为X的右孩子。

右旋转

就是使得以X节点为轴做右旋转，X节点的左孩子Y成为它的父节点，Y的右孩子成为X的左孩子。

实际的应用中会同时使用变色和旋转。

性能

整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。

实际应用

TreeMap和TreeSet，以及Java8中HashMap都是用的红黑树。