一、基本概念

我们来了解一种数据结构：二叉树。相信学过数据结构的同学知道，这种结构的数据存储形式在查找的时候效率非常高。

二叉树结构又可再细分为二叉查找树 叉平衡树

二叉查找树是一种有序的树：所有的左孩子的value值都是小于叶子结点的value值的，所有右孩子的value值都是大于叶子结点的。

这样做的好处在于：如果需要按照键值查找数据元素，只要比较当前结点的value值即可（小于当前结点value值的，往左走，否则往右走），这种方式，每次可以减少一半的操作，所以效率比较高。

比二叉查找树更进一步的是二叉平衡树，二叉平衡树除了保证有序外，还能够保持每个节点左右子树的高度相差不超过1。常见的平衡树有AVL树，Treap，红黑树，伸展树，等等。

红黑树是在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接*衡的。

在TreeMap中，即是使用了红黑树。

二、红黑树

具体性质如下：

1. 每个节点颜色不是黑色，就是红色
2. 根节点是黑色的
3. 如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）
4. 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点

那么为什么当满足以上性质时，就能保证最长路径不超过最短路径的二倍了呢？我们分析一下：