红黑树

1. 每个节点只能是红色或者黑色（废话）

2. 根节点必须是黑色。

3. 红色的节点，它的叶节点只能是黑色。（不能有2个连续的红色节点）

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

由以上四个特性我们可以看出一些红黑树的特点：

**最长路径长度 <= 2×最短路径 **

从根节点到最远叶节点的路径（最远路径）肯定不会大于根节点到最近节点的路径（最短路径）的两倍长。这是因为性质 3 保证了没有相连的红色节点，性质 4 保证了从这个节点出发的不管是哪一条路径必须有相同数目的黑色节点，这也保证了有一条路径不能比其他任意一条路径的两倍还要长。

因此，红黑树兼顾了平衡和插入性能，不会退化成链表，又不会像完全二叉树一样频繁的触发树高的调整。