Java TreeMap源码解析

四、红黑树性质

先看看红黑树的样子：

叶子节点为上图中的NIL节点，国内一些教材中没有这个NIL节点，我们在画图时有时也会省略这些NIL节点，但是我们需要明确，当我们说叶子节点时，指的就是这些NIL节点。

红黑树通过下面5条规则，保证了树是平衡的：

树的节点只有红与黑两种颜色

根节点为黑色的

叶子节点为黑色的

红色节点的字节点必定是黑色的

从任意一节点出发，到其后继的叶子节点的路径中，黑色节点的数目相同

满足了上面5个条件后，就能够保证：根节点到叶子节点的最长路径不会大于根节点到叶子最短路径的2倍。 其实这个很好理解，主要是用了性质4与5，这里简单说下：

假设根节点到叶子节点最短的路径中，黑色节点数目为B，那么根据性质5，根节点到叶子节点的最长路径中，黑色节点数目也是B，最长的情况就是每两个黑色节点中间有个红色节点（也就是红黑相间的情况），所以红色节点最多为B－1个。这样就能证明上面的结论了。

五、红黑树操作

关于红黑树的插入、删除、左旋、右旋这些操作，我觉得最好可以做到可视化，文字表达比较繁琐，我这里就不在献丑了，网上能找到的也比较多，像v_July_v的《教你透彻了解红黑树》。我这里推荐个swf教学视频（视频为英文，大家不要害怕，重点是看图??），7分钟左右，大家可以参考。 这里还有个交互式红黑树的可视化网页，大家可以上去自己操作操作，插入几个节点，删除几个节点玩玩，看看左旋右旋是怎么玩的。

六、总结

TreeMap的key是有序的，增删改查操作的时间复杂度为O(log(n))，为了保证红黑树平衡，在必要时会进行旋转

HashMap的key是无序的，增删改查操作的时间复杂度为O(1)，为了做到动态扩容，在必要时会进行resize。