Java数据结构之红黑树
红黑树的特点：
- 每个结点不是红的就是黑的；
- 根结点总是黑色的；
- 每个叶子结点都是黑色的空结点（NIL结点）；
- 如果结点是红色的，则它的叶子结点必须是黑色的（反之不一定），即从每个叶子到根的所有路径上不能有两个连续的红色结点；
- 从根结点到叶子结点或空结点的每条路径，必须包含相同数目的黑色结点（即相同的黑色高度）；
红黑树的应用：
TreeMap、TreeSet 以及 JDK 1.8 的 HashMap 底层都用到了红黑树。
为什么要用红黑树？
简单来说就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
二叉查找树（BST）具备什么特性呢？
- 左子树上所有结点的值均小于或等于他的根结点的值；
- 右子树上所有节点的值均大于或等于他的根节点的值；
- 左、右子树也分别为二叉排序树。
