上一篇文章我们讲了如何通过二分查找进行搜索，今天这篇文章，我们介绍二分查找的高级版，即二叉查找树。二叉查找树主要解决的问题是查找表，查找表的概念和我们了解的字典结构非常像，简单说就是根据一个key值，然后查找该key值对应的value值。类似这种数据结构，在计算机的算法中非常常见，有着非常广泛的应用。今天我们主要介绍二叉查找树的三个主题：

一是如何构建一棵二叉查找树；

二是在二叉查找树中如何进行查找；

三是检验二叉查找树的搜索效率是不是真的高。

好，下面我们进入主题。

构建二叉查找树

二叉查找树的性质如下：首先它就是一棵普通的二叉树，但是满足左子树中节点的key值都小于根节点的key值，右子树中节点的key值都大于根节点的key值，同时当把左右子树分别当做一棵二叉树的时候，继续满足上述条件。二叉查找树就是有这么一个非常好的递归性质，其余的它既不是满二叉树，也不是完全二叉树。

那根据上面的性质，构建二叉树的过程是什么样的呢？请看下图：

二叉查找树的构建过程

对于一棵二叉查找数，当插入一个节点的时候，主要过程如下：

1）和当前节点的key值进行比较；

2）如果当前节点为NULL，则将该节点插入该位置；

3）如果和当前节点相等（如果是key-value形式，一般是更新value值），则返回；

4）如果比当前节点小，则和该节点的左孩子节点中的key值进行比较，即跳回1）；

5）如果比当前节点大，则和该节点的右孩子节点中的key值进行比较，即跳回1）；

这是一个非常好的递归性质，下面我们就以C++语言为基础，来看看如何实现一个二叉查找树。

二叉查找树的基础

如上面代码所示，我们定义了一个二叉查找树类。在该类中，首先定义了一个节点STRUCT。在该Node中，有相应的key和value值，同时还有左节点和右节点的指针。这基本上就包括了一棵二叉树的基本构造。其次，在二叉查找树中还有一个根节点，该根节点一直指向二叉查找树的根。最后，还有一个计数器用于存储该二叉查找树中节点的个数。

好，基本构造介绍完，下面我们就看如何插入一个节点：

二叉查找树的插入

插入函数是一个非常经典的递归实现。对于递归实现，实现逻辑和上面的语言描述是一致的，希望你也能写这么一段代码。其实递归算法，你只要找好结束条件，那实现起来就非常简单。

二叉查找树的查找

既然叫二叉查找树，那最关键的逻辑肯定是如何进行查找（其实不是最难的）。查找的过程其实和插入的过程基本上是一致，但查找只是一个遍历的过程，能够找到则返回key对应的value值，如果不能找到，则返回定义好的错误状态（这个错误状态怎么定义很关键，后面我们会细说）。首先我们看一个示意图：

二叉查找树的查找过程

根据上面的示意图，我们可以这么定义算法：

1）和当前节点的key值进行比较；

2）如果当前节点为NULL，则返回不存在key值的错误状态；

3）如果和当前节点相等（如果是key-value形式，一般是更新value值），则返回value值；

4）如果比当前节点小，则和该节点的左孩子节点中的key值进行比较，即跳回1）；

5）如果比当前节点大，则和该节点的右孩子节点中的key值进行比较，即跳回1）；

那在2）中当比较的节点为NULL时，我们该怎么返回key值不存在的错误状态呢，这就要从源码的实现来说起了。首先，我们还是先看一下具体的源码实现：

二叉查找树的查找源码

从源码中可以看出来，我实现了两个函数，一个是包含函数，即contain；一个是真正的查找函数，即search。一般情况这两个函数是配合使用，先使用contain查找一下key值是否存在，如果存在则再调用search函数返回该key值对应的value值。C++和Java的很多类库确实是这么实现的，但是总是有很多菜鸟程序员不按照套路出牌，没有调用contain就调用search函数查找key值对应的value值。这个时候search函数就有可能存在key值无法找到情况，那search函数的返回值设定就比较关键了（这就是我们前面说的如何定义查找失败时的错误状态）。

我们源码的返回值是Value类型的指针。其实还有两种情况也可以考虑，但都没有返回Value类型的指针靠谱：

1）返回Node类型的指针。因为Node类型使我们在二叉查找树中定义的私有类，所以返回这种类型的指针，显然破坏了类的封装性；

2）返回Value类型。这种返回类型最大的问题就是当key值不存在时，value返回什么值都不合理。

所以，结合目前来看，返回Value类型的指针，基本是最合适的解决方案。

二叉查找树的效率

说了这么多二叉查找树的实现算法，那二叉查找树的查找效率究竟如何呢，下面我们就用一个实验来验证一下。这个实验的目的是：统计《圣经》全文中god这个单词出现的词频。具体的实验过程是这样的：

1）首先以单词作为key，词频作为value构造一个节点数据类型；

2）统计《圣经》中的所有单词，然后将各个单词所在的Node插入的两种数据结构中；

3）一种数据结构是二叉查找树，另一种数据结构是顺序表；

4）分别在这两个数据结构中，寻找god这个单词的词频，看看哪个数据结构的效率更高。

所谓的顺序表，就是将统计好词频的Node节点按照顺序插入到该表中。也就是说顺序表的查找过程就是简单粗暴的从头查到尾。那这两个数据结构的查找效率是怎么样的呢，请看下图：

二叉查找树的效率

从上面的结果可以看出来，《圣经》中一共有43万多个单词，而god这个单词一共出现了2301次。而查找的效率可以说是天壤之别。二叉查找树的查找时间是1秒多一点，而顺序表则是用了接近100秒，相差了两个数量级。可见，如此简单的一个算法，不同的数据结构效率却差如此之多。而且说实话《圣经》中单词的数据量可不算大，如果数据量再大一些，相差的效率只会更大。

另外，对于顺序表以及整个比较过程的实现源码，希望你能够自己实现一下（实现过程有一定难度，但没有你想的那么难）。我是徐建航，这是我写的第71篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。