红黑树

红黑树的特性？应用？优势？什么情况下变色？什么情况下旋转？

https://juejin.im/post/5a27c6946fb9a04509096248#comment

红黑树是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，还具备以下特性：

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4.每个红色节点的两个子节点都是黑色，反之不一定。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到每个叶子节点的所有路径都包含相同数目的黑色节点。

因这些规则限制，才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。

红黑树的应用？

集合类TreeSet、TreeMap以及JDK1.8之后的HashMap底层都用到了红黑树。

为什么要用红黑树？/ 优势？

解决二叉查找树的缺陷，因二叉查找树多次插入新节点导致不平衡，退化成一个线性结构。