原文地址：https://www.cnblogs.com/LiaHon/p/11221634.html

前面我们分别讲了Map接口的两个实现类HashMap和LinkedHashMap，本章我们讲一下Map接口另一个重要的实现类TreeMap，TreeMap或许不如HashMap那么常用，但存在即合理，它也有自己的应用场景，TreeMap可以实现元素的自动排序。

一. TreeMap概述

1. TreeMap存储K-V键值对，通过红黑树（R-B tree）实现；
2. TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现；
3. TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；
4. TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；

二. 红黑树回顾

因为TreeMap的存储结构是红黑树，我们回顾一下红黑树的特点以及基本操作，红黑树的原理可参考关于红黑树(R-B tree)原理，看这篇如何。下图为典型的红黑树：

红黑树规则特点：

1. 节点分为红色或者黑色；
2. 根节点必为黑色；
3. 叶子节点都为黑色，且为null；
4. 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
5. 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
6. 新加入到红黑树的节点为红色节点；

红黑树自平衡基本操作：