貌似k＝3时比k＝2时得到的结果还要小，那也是说三叉搜索树应该比二叉搜索树更好些呀，但是为什么二叉树更流行呢？后来在的stackoverflow上找到了答案，主旨如下：
　　现在的CPU可以针对二重逻辑（binary logic）的代码做优化，三重逻辑会被分解为多个二重逻辑。
　　这样也大概能理解为什么二叉树这么流行了，是因为进行一次比较操作，我们多可以将问题规模减少一半。 好了这里扯的有点远了，我们再回到红黑树上来。
　　红黑树性质
　　先看看红黑树的样子：

　　红黑树示例
　　上图是从wiki截来的，需要说明的一点是：
　　叶子节点为上图中的NIL节点，国内一些教材中没有这个NIL节点，我们在画图时有时也会省略这些NIL节点，但是我们需要明确，当我们说叶子节点时，指的是这些NIL节点。
　　红黑树通过下面5条规则，保证了树是平衡的：
　　树的节点只有红与黑两种颜色
　　根节点为黑色的
　　叶子节点为黑色的
　　红色节点的字节点必定是黑色的
　　从任意一节点出发，到其后继的叶子节点的路径中，黑色节点的数目相同
　　满足了上面5个条件后，能够保证：根节点到叶子节点的长路径不会大于根节点到叶子短路径的2倍。 其实这个很好理解，主要是用了性质4与5，这里简单说下：
　　假设根节点到叶子节点短的路径中，黑色节点数目为B，那么根据性质5，根节点到叶子节点的长路径中，黑色节点数目也是B，长的情况是每两个黑色节点中间有个红色节点（也是红黑相间的情况），所以红色节点多为B－1个。这样能证明上面的结论了。
　　红黑树操作

　　红黑树旋转示例（没有画出NIL节点）
　　关于红黑树的插入、删除、左旋、右旋这些操作，我觉得好可以做到可视化，文字表达比较繁琐，我这里不在献丑了，网上能找到的也比较多，像v_July_v的《教你透彻了解红黑树》。我这里推荐个swf教学视频（视频为英文，大家不要害怕，重点是看图??），7分钟左右，大家可以参考。 这里还有个交互式红黑树的可视化网页，大家可以上去自己操作操作，插入几个节点，删除几个节点玩玩，看看左旋右旋是怎么玩的。
　　源码剖析
　　由于红黑树的操作我这里不说了，所以这里基本上也没什么源码可以讲了，因为这里面重要的算法都是From CLR，这里的CLR是指Cormen， Leiserson， Rivest，他们是算法导论的作者，也是说TreeMap里面算法都是参照算法导论的伪代码。 因为红黑树是平衡的二叉搜索树，所以其put（包含update操作）、get、remove的时间复杂度都为log(n)。
　　总结
　　到目前为止，TreeMap与HashMap的的实现算是都介绍完了，可以看到它们实现的不同，决定了它们应用场景的不同：
　　TreeMap的key是有序的，增删改查操作的时间复杂度为O(log(n))，为了保证红黑树平衡，在必要时会进行旋转
　　HashMap的key是无序的，增删改查操作的时间复杂度为O(1)，为了做到动态扩容，在必要时会进行resize。
　　另外，我这里没有解释具体代码，难免有些标题党了，请大家见谅，后面理解的更深刻了再来填坑。