史上最全的二叉搜索树（一）：红黑树

public class TreeMap
       extends AbstractMap
       implements NavigableMap, Cloneable, java.io.Serializable

可以看出，相比而言，多继承了一个接口，也就是这个接口，这决定了区别于：

键是无序的，键是有序的

界面

先看签名

public interface NavigableMap extends SortedMap

发现继承了继承，再看签名

public interface SortedMap extends Map

就像它的名字一样，它意味着这个 Map 是有序的。这个顺序一般是指接口提供的键的自然顺序（ ），也可以在创建实例时指定一个来确定。当我们使用集合视图（视图，也由 and 方法提供）的实例时，会反映键的顺序。这是和之间差异的扩展（请参阅此处）：

插入键的类必须继承该类（或指定一个），以确定如何比较（通过（k2)或pare（k1，k2)））这两个键，否则，在插入的时候会报异常，也就是方法中key的顺序要和方法一致，也就是说(k2) or pare(k1, k2)是真的，k1.(k2)也应该是真的。介绍完再回到我们。是JDK的新增1.6。在JDK的基础上< @1.6，添加了一些“导航方法”。（）返回最接近搜索目标的元素。例如，以下方法：

设计理念 ( ) 红黑树

它是使用红黑树作为基础来实现的。红黑树是二叉搜索树。让我们一起回忆一下二叉搜索树的一些性质。

二叉搜索树

我们来看看二叉搜索树（treejava实现二叉树带权路径长度，BST）长什么样子？

二叉搜索树

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

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

二叉搜索树的优点是每做一次判断，问题的大小就可以减半，所以如果二叉搜索树是平衡的，找到一个元素的时间复杂度是log(n)，即是树的高度。我在这里想到了一个更严肃的问题。如果二叉搜索树将问题大小减少一半，那么三叉搜索树将问题大小减少三分之二。不是更好吗，等等，我们还可以有四叉搜索树，五叉搜索树……对于更一般的情况：

有n个元素，K-ary树搜索树的K为多少时效率最好？当K=2？

K-ary搜索树

如果按照我上面的分析，你也可能会陷入一个误区，那就是

当三叉搜索树将问题大小减少三分之二时，所需的比较操作数为两次（当二叉搜索树将问题大小减少一半时，只需进行一次比较操作）

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

对于 n 个元素，K-ary 树搜索树所需的平均比较次数为 k*log(n/k)。

对于k=n的极端情况，将K-ary树转化为线性表，复杂度为O(n)。如果从数学的角度来解决这个问题，就相当于：

当n为固定值时，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。可以看出二叉树基本上是最优解。在 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时得到的结果要小，也就是说三叉查找树应该比二叉查找树要好，但是为什么二叉查找树更受欢迎呢？后来在万能上找到了答案，主旋律如下：

今天的 CPU 可以针对双逻辑优化代码java实现二叉树带权路径长度，三重逻辑被分解为多个双逻辑。

这也大致理解了二叉树为何如此受欢迎的原因，因为通过进行比较操作，我们最多可以将问题规模缩小一半。好了，这就扯远了，我们回到红黑树上。

红黑树性质

我们先来看看红黑树：

红黑树示例

上图取自维基。应该注意的是：

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

红黑树通过以下五个规则确保树平衡：

树的节点只有两种颜色，红色和黑色。根节点是黑色的。叶节点是黑色的。红色节点的字节点必须是黑色的。从任何节点开始，到其后续叶节点的路径中的黑色节点数。相同的

满足以上五个条件后，可以保证根节点到叶子节点的最长路径不会大于根节点到叶子节点的最短路径的两倍。事实上，这很容易理解。它主要使用属性4和5。这里简单说明一下：

假设在根节点到叶子节点的最短路径中，黑色节点的数量为B，那么根据性质5，在根节点到叶子节点的最长路径中，黑色节点的数量也是B ，最长的情况是在每两个黑色节点之间。有一个红色节点（即红黑情况），所以红色节点最多为B-1。这证明了上述结论。

红黑树操作

红黑树旋转示例（不绘制NIL节点）

关于红黑树的插入、删除、左旋、右旋的操作，我觉得最好形象化一下。文字表达比较繁琐。彻底了解红黑树。我这里推荐一个swf教学视频（视频是英文的，别怕，关键是看图？？），7分钟左右，可以参考。还有一个交互式红黑树的可视化网页。可以自己上去操作，插入几个节点，删除几个节点玩，看看左撇子和右撇子怎么玩。

源码分析

由于这里不讲红黑树的操作，所以这里基本没有源码可以讲，因为这里重要的算法都是来自CLR，这里CLR指的是，，，，他们是算法简介，也就是说里面的算法是伪代码，参考算法简介。因为红黑树是平衡二叉搜索树，所以它的put（包括操作）、get、get的时间复杂度为log(n)。

总结

至此，和的实现已经介绍过了，可以看到它们实现的不同，这决定了它们在应用场景上的不同：

转发+关注私信我会回复今日头条666接收信息

文章来源:http://www.toutiao.com/a6854920370474975758/

感谢您的来访，获取更多精彩文章请收藏本站。