五、红黑树

红黑树特点 :

1. 每个节点非红即黑；
2. 根节点总是黑色的；
3. 每个叶子节点都是黑色的空节点（NIL节点）；
4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

红黑树的应用 ：TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。
为什么要用红黑树？ 简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 漫画：什么是红黑树？open in new window（也介绍到了二叉查找树，非常推荐）

二叉查找树（BST）具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。

相关阅读 ：《红黑树深入剖析及Java实现》open in new window（美团点评技术团队）