Java TreeMap源码解析

三、设计理念（design concept）

TreeMap是用红黑树作为基础实现的，红黑树是一种二叉搜索树，让我们在一起回忆下二叉搜索树的一些性质

二叉搜索树

先看看二叉搜索树（binary search tree，BST）长什么样呢？。

相信大家对这个图都不陌生，关键点是：

左子树的值小于根节点，右子树的值大于根节点。

二叉搜索树的优势在于每进行一次判断就是能将问题的规模减少一半，所以如果二叉搜索树是平衡的话，查找元素的时间复杂度为log(n)，也就是树的高度。 我这里想到一个比较严肃的问题，如果说二叉搜索树将问题规模减少了一半，那么三叉搜索树不就将问题规模减少了三分之二，这不是更好嘛，以此类推，我们还可以有四叉搜索树，五叉搜索树……对于更一般的情况：

n个元素，K叉树搜索树的K为多少时效率是最好的？K＝2时吗？

K 叉搜索树

如果大家按照我上面分析，很可能也陷入一个误区，就是

三叉搜索树在将问题规模减少三分之二时，所需比较操作的次数是两次（二叉搜索树再将问题规模减少一半时，只需要一次比较操作）

我们不能把这两次给忽略了，对于更一般的情况：

n个元素，K叉树搜索树需要的平均比较次数为k*log(n/k)。

对于极端情况k＝n时，K叉树就转化为了线性表了，复杂度也就是O(n)了，如果用数学角度来解这个问题，相当于：

n为固定值时，k取何值时，k*log(n/k)的取值最小？

k*log(n/k)根据对数的运算规则可以转化为ln(n)*k/ln(k)，ln(n)为常数，所以相当于取k/ln(k)的极小值。这个问题对于大一刚学高数的人来说再简单不过了，我们这里直接看结果

当k＝e时，k/ln(k)取最小值。

自然数e的取值大约为2.718左右，可以看到二叉树基本上就是这样最优解了。在Nodejs的REPL中进行下面的操作

function foo(k) {return k/Math.log(k);} > foo(2) 2.8853900817779268 > foo(3) 2.730717679880512 > foo(4) 2.8853900817779268 > foo(5) 3.1066746727980594

貌似k＝3时比k＝2时得到的结果还要小，那也就是说三叉搜索树应该比二叉搜索树更好些呀，但是为什么二叉树更流行呢？后来在万能的stackoverflow上找到了答案，主旨如下：

现在的CPU可以针对二重逻辑（binary logic）的代码做优化，三重逻辑会被分解为多个二重逻辑。

这样也就大概能理解为什么二叉树这么流行了，就是因为进行一次比较操作，我们最多可以将问题规模减少一半。 好了这里扯的有点远了，我们再回到红黑树上来。