初识TreeMap

之前的文章讲授了两种Map，别离是HashMap与LinkedHashMap，它们担保了以O(1)的时间巨大度举办增、删、改、查，从存储角度思量，这两种数据布局长短常优秀的。别的，LinkedHashMap还特别地担保了Map的遍历顺序可以与put顺序一致，办理了HashMap自己无序的问题。

尽量如此，HashMap与LinkedHashMap照旧有本身的范围性—-它们不具备统计机能，可能说它们的统计机能时间巨大度并不是很好才更精确，所有的统计必需遍历所有Entry，因此时间巨大度为O(N)。好比Map的Key有1、2、3、4、5、6、7，我此刻要统计：

1. 所有Key比3大的键值对有哪些
2. Key最小的和Key最大的是哪两个

就雷同这些操纵，HashMap和LinkedHashMap做得较量差，此时我们可以利用TreeMap。TreeMap的Key凭据自然顺序举办排序可能按照建设映射时提供的Comparator接口举办排序。TreeMap为增、删、改、查这些操纵提供了log(N)的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的O(1)时间巨大度要差些；可是在统计机能上，TreeMap同样可以担保log(N)的时间开销，这又比HashMap与LinkedHashMap的O(N)时间巨大度好不少。

因此总结而言：假如只需要存储成果，利用HashMap与LinkedHashMap是一种更好的选择；假如还需要担保统计机能可能需要对Key凭据必然法则举办排序，那么利用TreeMap是一种更好的选择。

红黑树的一些根基观念

在讲TreeMap前照旧先说一下红黑树的一些根基观念，这样可以更好地领略之后TreeMap的源代码。

二叉查找树是在生成的时候长短常容易失衡的，造成的最坏环境就是一边倒（即只有左子树/右子树），这样会导致树检索的效率大大低落。（关于树和二叉查找树可以看我之前写的一篇文章树型布局）

红黑树是为了维护二叉查找树的均衡而发生的一种树，按照维基百科的界说，红黑树有五个特性，但我以为讲得不太易懂，我本身总结一下，红黑树的特性大抵有三个（换句话说，插入、删除节点后整个红黑树也必需满意下面的三本性质，假如不满意则必需举办旋转）：

1. 根节点与叶节点都是玄色节点，个中叶节点为Null节点
2. 每个赤色节点的两个子节点都是玄色节点，换句话说就是不能有持续两个赤色节点
3. 从根节点到所有叶子节点上的玄色节点数量是沟通的

上述的性质约束了红黑树的要害：从根到叶子的最长大概路径不多于最短大概路径的两倍长。获得这个结论的来由是：

1. 红黑树中最短的大概路径是全部为玄色节点的路径
2. 红黑树中最长的大概路径是红黑相间的路径

此时（2）正好是（1）的两倍长。功效就是这个树大抵上是均衡的，因为好比插入、删除和查找某个值这样的操纵最坏环境都要求与树的高度成比例，这个高度的理论上限答允红黑树在最坏环境下都是高效的，而差异于普通的二叉查找树，最终担保了红黑树可以或许以O(log2 n) 的时间巨大度举办搜索、插入、删除。

下面展示一张红黑树的实例图：

可以看到根节点到所有NULL LEAF节点（即叶子节点）所颠末的玄色节点都是2个。

别的从这张图上我们还能获得一个结论：红黑树并不是高度的均衡树。所谓均衡树指的是一棵空树或它的阁下两个子树的高度差的绝对值不高出1，可是我们看：

阁下子树的高度差值为2，因此红黑树并不是高度均衡的，它放弃了高度均衡的特性而只追求部门均衡，这种特性低落了插入、删除时对树旋转的要求，从而晋升了树的整体机能。而其他均衡树好比AVL树固然查找机能为机能是O(logn)，可是为了维护其均衡特性，大概要在插入、删除操纵时举办多次的旋转，发生较量大的耗损。

四个存眷点在LinkedHashMap上的谜底

TreeMap根基数据布局

TreeMap基于红黑树实现，既然是红黑树，那么每个节点中除了Key–>Value映射之外，一定存储了红黑树节点特有的一些内容，它们是：

1. 父节点引用
2. 左子节点引用
3. 右子节点引用
4. 节点颜色