算法导论随笔(五)：二叉搜索树和霍夫曼编码

上一篇文章中讨论了树这种数据结构，以及其衍生的二叉树。这篇文章中，主要讨论二叉树的衍生树以及基于二叉树的算法。

1.二叉搜索树

二叉搜索树是由二叉树衍生出的一个高级数据结构，具备了二叉树的所有特性。二叉搜索树的每一个内部节点(internal node)都存储了一个键（或一对键值对）。二叉搜索树的叶子节点不存储任何东西。在此基础上，设x是二叉搜索树中的任意一个节点，x有如下性质：
若y是x左子树中的一个节点，则有
$y.key \le x.key$y.key≤x.key
若y是x右子树中的一个节点，则有
$y.key \ge x.key$y.key≥x.key
下图就是一个二叉搜索树。以根节点为例，该节点的key值为6。该节点的左子树中，有三个内部节点，key值分别为1，2，4，均小于根节点的key值。在跟节点的右子树中，有两个内部节点，key值分别为8和9，均大于根节点的key值。

2.二叉搜索树的查找

二叉搜索树的查找指的是对于一个节点key值的查找。假设我们要找的key值为k。查找的顺序是从根节点开始，从上至下。首先访问根节点，判断该节点的key值是否为目标值。若不是，则访问下一个节点：若目标值小于当前访问的节点key值，则访问左子树的节点；反之则访问右子树的节点。二叉搜索树的查找过程的伪代码如下。
注：图中NIL表示叶子节点。

以上面的二叉搜索树为例，若我们想查找key为4的节点，则该过程形成的路径如下图所示。首先由于4小于6，则访问6的左子树，即2。接着由于4大于2，则访问2的右子树4。此时找到目标key值4，则返回该节点。

3. 二叉搜索树的插入

向二叉搜索树插入数据之前，要先对二叉搜索树进行查找。假设我们要插入的节点的key值为k，则首先在该二叉查找树内查找k。若树内已经有key值为k的节点，则返回指向该节点的指针。

下面重点要讨论的是树内没有key值为k的节点时，要插入key值为k的节点所需要的操作。由于key值为k的节点并不存在于树中，那么对这个节点的搜索一定会到达一个叶子节点。我们假设这个节点叫w，把k存储于w中，并给w扩展两个子节点，这两个子节点成为新的叶子节点。比如，对于上图中的二叉搜索树，若我们想插入key值为5，则插入后的二叉搜索树如下。

4. 二叉搜索树的删除

从二叉搜索树中删除节点之前，同样要先对二叉搜索树进行查找。假设我们想删除的节点的key值为k，则有以下三种情况。

1. 若该节点不存在（即查找过程返回一个叶子节点），则不做任何事情。
2. 若该节点存在，且该节点有一个子节点是叶子节点。设该节点是v，该节点的子节点w是叶子节点。则从二叉搜索树中删除v和w，并且将v的另一个子节点顶替至w原来的位置。
   例如，若要从上面插入了5之后的二叉树中删除4，则首先找到v和w：

接着删除v和w，将v的另一个子节点5移动至v在原先二叉树中的位置：

3. 若该节点存在，且该节点的两个子节点均不是叶子节点。也就是说，该节点为内部节点。我们给这个要删除的节点取名为v。在这种情况下，我们要找出该节点的右子树中的拥有最小key值的节点。这个节点叫w。此时，把w的key值赋给v。由于w在右子树中拥有最小key值，则该节点的左子节点一定是叶子节点，否则根据二叉搜索树的性质，该节点的key值一定比w小，与w为右侧子树中最小key值的节点矛盾。接着，我们删除w的左子节点z，并把w的右子节点节点顶至w的位置。
   例如，若想从下图中的二叉搜索树删除3，我们先找出该二叉树中的v，w和z。
   
   删除节点后，新的二叉搜索树如下。可以看到w的key值5被拿来替换v的key值，因此v的新key值为3。w和其左子节点被移除，w的右子树(也是一个叶子节点)顶替至w原来的位置。
   

5. 霍夫曼编码Huffman coding

霍夫曼编码是一种基于二叉树的计算机编码方式。在编码中，以数字0和1的组合来表示所有英文字符。那么就存在一个问题，比如以01来代表a，010来代表b。那么对于010…这串编码来说，就很容易产生歧义，因为计算机可能并不知道要把开头的01解释为a，还是要把010解释为b。因此，对于所有字母，我们必须要规定它们都有自己独一无二的前缀，使得在任何一种情况下，一串编码永远会被解析成唯一的原文。例如如下编码方式

那么这段编码方式是如何与二叉树产生联系的呢？我们知道对于一个二叉树的节点，它可以有左子节点和右子节点。那么我们用连接该节点与其左子节点的树枝代表0，用连接该节点与其右子节点的树枝代表1，就可以用下图中的二叉树来表示上图中的5个字母。

从根节点开始，查看其到所有叶子节点的路径：00表示a，010表示b，011表示c，10表示d，11表示e。
我们可以看到，图中并非所有叶子节点的深度都相同。也就是说，如果想表示a，我们只需要两个数字即可；但若想表示b，就需要三个数字。

那么问题来了，如果我想转换一段文字，该用什么样的策略，使得转换后的码文最短呢？比如，原文里有大量的字母b，而只有很少的字母a，那么上图中的编码方式显然不是最优解，因为每个字母b要占用3个字节，大量字母b就会占用更多的字节。再比如，abbb这个字符串，若字母a用10表示，字母b占用111表示，则编码后的码文为10111111111，长度为11。若反过来用111表示a，用10表示b，则码文为111101010，长度只有9。若我们想通过网络传输码文，那么很明显越长的码文就需要更多的带宽消耗。因此，我们要寻求一个编码方式，使得编码后的码文最短。

霍夫曼编码（也称霍夫曼算法）完美解决了这个问题。该算法对原文使用到的所有字母计算它出现的次数，并把这些字母按出现次数从少到多排列起来。这个算法的中心思想就是，让出现次数最多的字母节点在二叉树中有最小的深度；让出现次数最少的字母有最大的深度。这样一来，常出现的字母可能只占1个字节，该字母出现的频率越高则节省的空间越大。该算法的伪代码如下：

算法的输入是一串长度为n的字符串，该字符串中包含d个不同字母。
算法的输出是该字符串的编码树。

下面用一个例子说明该算法的原理。假设我们要对一串原文进行编码：abracadabra。
首先，计算该原文中每个字母出现的次数。如下图所示。接着为每个字母创建一个键值对，key为该字母出现次数，value为该字母。把这5个键值对存入一个优先级队列中。该队列以键值对的key值从小到大排列。因此，该队列为{1:c, 1:d, 2:r, 2:b, 5:a}。

接着，为每一个字母创建一个只有一个节点的二叉树，二叉树的头结点存储该字母的出现次数。因此，我们得到如下五棵二叉树。

接着，从优先级队列中先取出（并删除）两个key最小的键值对，将这两个键值对key值的和作为一个新的二叉树的根节点，这两个键值对的value值(也就是字母)作为该根节点的两个子节点。然后将该新二叉树插入至优先级队列中。该操作后，现有的二叉树变为4棵，如下图

优先级队列变为{2:r, 2:b, 2:cd, 5:a}。

接下来继续重复刚才的操作，从优先级队列中拿出两个最小key值的键值对，即b和r，现有二叉树变为

优先级队列变为{2:cd, 4:rb, 5:a}。
接下来取出2和4的键值对，二叉树变为

优先级队列变为{5:a, 6:rbcd}。
最后，取出优先级队列中仅剩的两个键值对5和6，二叉树变为

上图也就是我们得出的最终二叉树。从这个二叉树可得出每个字母的编码：
a: 0
c:100
d:101
b:110
r:111

可以看出，在中间的一些步骤中，优先级队列中可能存在3个或更多个最小key值的键值对。对于3个或以上优先级相同的键值对，取出2个键值对的操作，其结果可能因平台不同而异。也就是说，该算法的结果并不一定唯一，但可以保证的是，不同的结果产生的编码，其最终长度都同样最小，因为不同的结果二叉树导致的变化值存在于字符编码中的某些1变为0，0变为1，例如110变为111，但其需要的编码长度唯一。

6.写在最后

霍夫曼编码的复杂度为
$T(n) = O(n + d log d)$T(n)=O(n+dlogd)
其中n为输入字符串的长度，d为该字符串中不同字母的数量。我们假设最坏情况，n中每一个字母都是独一无二的，则n=d，算法复杂度可简化为
$T(n) = O(n + n log n) = O(n log n)$T(n)=O(n+nlogn)=O(nlogn)
霍夫曼编码是一种基于二叉树的算法，同时他也是贪心算法(greedy algorithm，也称贪婪算法) 的一个实例。今后我会对贪心算法进行更多的分析与介绍。