1.6 树

树是一种由有限节点组成的具有层次关系的集合，把它叫作树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下。每个节点有零个或多个子节点，没有父节点的节点称为根节点，除了根节点以外，每个节点都有且仅有一个父节点，并且树里面没有环路。空集合也是树，称为空树，空树中没有节点。

1. 树的常见术语

父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。

子节点：一个节点含有的子树的根节点称为该节点的子节点。

叶子节点：没有子节点的节点称为叶子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点。

节点的度：一个节点含有的子节点的个数称为该节点的度。

树的度：一棵树中，最大节点的度称为树的度。

节点的层次：根节点的层次为1，其他节点的层次等于它父节点的层次数加1。

节点的深度：根节点的深度为0，其他节点的深度等于它父节点的深度数加1。

树的深度：距离根节点最远的节点的深度即为树的深度。

节点的高度：所有叶子节点的高度为0，其他节点的高度等于它所有子节点中的最大高度加1。

树的高度：从根节点到达一个叶子节点的最长路径长度。

堂兄弟节点：父节点在同一层的节点互为堂兄弟节点。

节点的祖先：从根节点到该节点这条分支上的所有节点。

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：指若干棵互不相交的树的集合。

树的种类比较多，我们只介绍一些常见的树，这里先简单介绍3种，还有一些会在后面详细介绍。

二叉树：每个节点最多含有两个子树的树称为二叉树。

完全二叉树：对于一棵二叉树，除了最下面一层外，其他各层的节点数目均已达最大值，且最后一层的所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。

满二叉树：所有叶节点都在同一层的完全二叉树称为满二叉树，如图1-24所示，中间的二叉树，虽然上面各层的节点数目都已达到最大值，但最后一层的节点不是从左往右紧密排列的，所以它不是完全二叉树。

2. 完全二叉树的特性

•第i层上的节点数目最多为2^(i-1)。

•度为1的节点仅有1个或0个（叶子节点尽可能往左排）。

•叶子节点的个数=(n+1)/2 (n是二叉树所有节点的数量)。

如果我们让完全二叉树的根节点编号为0，把其他节点从上到下、从左到右逐个编上号，会有下面的对应关系。

3. 满二叉树的特性

•共有（2^k）-1个节点（k是总的层数）。

•节点个数一定是奇数。

•第i层有2^(i-1)个节点。

•有(n+1)/2个叶子节点（n是总的节点数量）。

•叶子节点的度都为0，非叶子节点的度都是2，没有度为1的节点。

1.6.1 二叉搜索树

二叉搜索树（Binary Search Tree）也叫作二叉查找树，它是具有下列性质的一种二叉树。

•若左子树不空，则左子树上所有节点的值都小于根节点的值；

•若右子树不空，则右子树上所有节点的值都大于根节点的值；

•任意节点的子树也都是二叉搜索树。

二叉搜索树有一个重要的特性就是它的中序遍历结果一定是有序的。如图1-25所示，二叉搜索树的中序遍历结果是[1,3,4,6,8,9]。

1. 二叉搜索树的查找

二叉搜索树的查找可以通过递归的方式，也可以通过while循环的方式，原理都一样，如图1-26所示，步骤如下：

•如果当前节点为空，则搜索失败。

•如果当前节点的值等于要查找的值，则直接返回。

•如果要查找的值比当前节点小，就往当前节点的左子树找。如果要查找的值比当前节点值大，就往当前节点的右子树找。

2. 二叉搜索树的插入

二叉搜索树插入的时候首先要找到它需要插入的位置，然后插入，如图1-27所示，步骤如下：

•如果当前节点为空，则直接创建一个新的节点返回。

•如果要插入的值比当前节点小，就往当前节点的左子树查找插入的位置。

•如果要插入的值比当前节点大，就往当前节点的右子树查找插入的位置。

以上使用的是递归的方式，递归将在第5章介绍。如果看不明白，还可以使用非递归方式。

3. 二叉搜索树的删除

二叉搜索树的删除相对来说要麻烦一些，如果删除的是叶子节点还好，可以直接删除。如果删除的节点只有一个子节点，可以让这个仅有的子节点替代它。如果删除的节点有两个子节点，我们就需要考虑删除当前节点后，子节点该怎样存放。在讲解二叉搜索树的删除之前，先来了解一下二叉树的前驱节点和后继节点。

前驱节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的前一个节点为该节点的前驱节点。

后继节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的后一个节点为该节点的后继节点。

如图1-28所示，二叉树中节点4的前驱节点是3，后继节点是5。假设要删除节点4，有两种方式。一种方式是让待删除节点的右子节点成为它前驱节点的右子节点，这样待删除的节点就只有一个子节点了，如图1-29所示。

还有一种方式是让待删除节点的左子节点成为它后继节点的左子节点，如图1-30所示。

这里的关键是怎样查找一个节点的前驱节点和后继节点，有的读者认为通过打印二叉树的中序遍历结果即可找到，但实际上不需要那么麻烦。一个节点的前驱节点是其左子树中的最大节点，那么这个节点就是其左子树往右一直走下去的节点。同理，一个节点的后继节点就是其右子树的最小节点，这个节点就是其右子树往左一直走下去的节点。

找到要删除节点的前驱节点或者后继节点，就可以将其删除了，删除的步骤如下，假设删除的节点是p：

•如果p是叶子节点，则直接删除。

•如果p不是叶子节点，并且p仅有一个子节点，只需要让p的父节点变成p的子节点的父节点即可，也可以理解为让p的子节点替换p的位置。

•如果p有两个子节点，就像上面讲的，有两种方式。一种方式是让p的右子节点成为它前驱节点的右子节点。还有一种方式是让p的左子节点成为它后继节点的左子节点，两种方式可以随便选一个。

注意：删除节点一般有两种实现方式，一种就是上面讲的，但这种方式有个缺点，就是会严重破坏树的平衡性。还有一种方式就是移形换位，不把待删除的节点删除，而是用它的前驱或者后继节点的值来替换它，然后把这个前驱或后继节点删除，后面讲AVL树和红黑树的时候会用这种方式。

1.6.2 AVL树

对于有n个元素的二叉搜索树，它的平均查找时间复杂度是O(logn)，但如果创建二叉搜索树的时候插入的是一组升序或者降序的数值，就会导致二叉搜索树始终偏向一方，变成类似链表的形状，查找时间复杂度变成了O(n)，如图1-31所示。

有没有一种方式不让它变成这种形状呢？实际上是有的，这就是本节要讲的AVL树（Adelson-Velsky and Landis Tree），AVL树得名于它的发明者G.M.Adelson-Velsky和Evgenii Landis。在AVL树中，任何节点的两个子树高度差小于等于1，所以它也被称为高度平衡树，增加和删除操作需要通过一次或多次旋转来重新平衡这棵树，我们先来看一下AVL树的节点类。

为了方便计算，我们在节点类中添加一个变量height，它表示当前节点的高度，默认叶子节点高度为1。如果没有这个变量，每次获取节点高度的时候，都需要重新计算一遍，增加了时间复杂度，而有了这个变量以后，每次使用的时候直接从节点中取即可。

在AVL树中，每个节点左子树与右子树的高度差称为节点的平衡因子，任一节点的平衡因子只能是-1、0和1，如果一个节点的平衡因子绝对值大于1，表示这棵二叉搜索树失去了平衡，不再是AVL树。

1. AVL树的插入

AVL其实就是一棵二叉搜索树，它的查找和前面讲的二叉搜索树的查找是一样的，查找操作就不介绍了，来看一下它的插入操作。AVL树的插入操作和二叉搜索树的插入操作类似，也是先找到待插入的位置，然后插入，因为AVL树是高度平衡的二叉搜索树，所以插入之后还需要进行调整，防止出现偏向一边的情况。

AVL树插入的时候为了保证树的平衡，会进行旋转，所以根节点不是固定的，每次插入的时候都需要更新根节点，所以插入的核心代码是add函数，我们看到它使用的是递归的实现方式，递归在这里非常重要，它最后一行的balanceTree函数是对树进行调整，也就是说它是自下往上一直到根节点，只要遇到不平衡的节点都会调整，我们暂时还没讲到递归，如果看不懂也没关系，只需要知道有这个过程就行。AVL树的节点在插入的时候会有4种情况，我们来分别看一下（小括号内数字表示左右子节点的高度差）。

情况一：LL类型

这种情况直接对不平衡的节点右旋即可，如图1-32所示。

情况二：LR类型

这种情况需要对不平衡节点的左子节点左旋，然后就会变成LL类型，接着对不平衡节点右旋，如图1-33所示。

情况三：RR类型

这种情况直接对不平衡节点左旋，如图1-34所示。

情况四：RL类型

这种情况需要对不平衡节点的右子节点右旋，然后就会变成RR类型，接着对不平衡节点左旋，如图1-35所示。

我们来整理一下：

到底是哪种类型，只需要计算每个节点的左右子树高度差即可判断，如果当前节点的左子树高度与右子树高度的差超过1，基本上可以判定是L（?）类型，那么？究竟是L还是R，还需要继续判断，判断方式直接看一下代码即可。

无论是左旋还是右旋，都会导致不平衡节点的高度发生改变，所以旋转之后还需要更新不平衡节点的高度，我们来看一下其他函数的代码。

再来看一下节点的左旋和右旋，先来看一下左旋，如图1-36所示，虽然它已经平衡了，但它并不影响我们对树旋转的研究。左旋是逆时针旋转两个节点，使不平衡节点被其右子节点取代，而该节点成为其右子节点的左子节点。左旋会导致不平衡节点以及它的右子节点高度发生变化，所以旋转之后它们的高度需要更新一下。

再来看一下右旋，如图1-37所示。右旋是顺时针旋转两个节点，使不平衡节点被其左子节点取代，而该节点成为其左子节点的右子节点。关于左旋和右旋的代码，大家可以直接通过图来理解，这里就不再逐步分析。

2. AVL树的删除

AVL树的删除，如果删除的是叶子节点或只有一个子节点的节点，则直接删除，否则使用移形换位法，用它的前驱节点或者后继节点替换它，然后删除它的前驱节点或者后继节点。我们看一下代码，注意删除的时候可能会出现不平衡，所以最后还需要进行调整。

我们回过头来看一下balanceTree这个函数，其中有下面两行代码。

旋转的时候其实就是哪边低先往哪边旋转，但如果两边子树高度都一样呢？如图1-38所示。

我们看到节点12出现了不平衡，而节点16的两个子树高度都是一样的，是按照RR处理还是按照RL处理呢？实际上尝试着旋转一下就知道，按照RR处理才能保证平衡。有的读者可能会说这个图是不可能存在的，因为它早已经出现了不平衡。实际上如果添加节点的时候，这个图是不会存在的，但删除的时候就不一定了，比如9还有一个节点，但我们把它删除了。

1.6.3 红黑树

AVL树是高度平衡的二叉搜索树，使用它主要是为了方便查找，以及减少查询次数，但如果添加和删除的次数比较多的时候，使用它显然就不合适了，因为它频繁地旋转，增加了算法的时间复杂度，这个时候就可以使用另外一种树——红黑树，红黑树也会旋转，但不会像AVL树那么频繁。红黑树有5个重要的性质。

（1）节点是红色或黑色。

（2）根节点是黑色。

（3）所有叶子都是黑色（叶子是null节点）。

（4）从根节点到所有的叶子节点的路径上不能有两个连续的红色节点。

（5）从任一节点到其每个叶子的路径都包含相同数目的黑色节点。

其中如果不理解第3条，基本上是搞不懂红黑树的，这里的叶子不是二叉树中定义的叶子节点，而是一种空的节点，它告诉我们任一节点如果只有一个子节点，那么该节点也是有两条路径的，这样就限制了另一条路径的长度。其实也在变相告诉我们红黑树中如果一个节点只有一个子节点，那么这个子节点必定是叶子节点，并且是红色的，结合第4和第5条就明白了。

红黑树中根到叶子的所有路径中，最长路径不会超过最短路径的两倍。可以反证一下，假设超过两倍会怎样？比如最短路径长度是a，最长路径长度是2a+1。根据性质4，路径上不能有两个连续的红色节点，即便最短路径上全部是黑色节点，那么在最长路径上也会有a+1个红色节点，因为根节点是黑色的，也就是说在剩下的a-1个黑色节点之间插入a+1个红色的节点，并且红色节点不能有连续的，无论如何也是做不到的，所以最长路径不可能超过最短路径的两倍。

1. 红黑树的插入

红黑树也是一棵二叉搜索树，它的查找、插入和删除可以参照前面讲的二叉搜索树和AVL树，不过在插入和删除之后，有可能打破树的平衡，所以在插入和删除之后，还需要进行调整，先来看一下红黑树插入的调整。

如果插入的是黑色节点，根据红黑树的性质5，肯定会破坏这一规则，所以这里插入的节点都是红色的。但插入红色节点有可能会破坏性质4，也有可能不会。如果没有破坏就不需要调整，如果破坏我们再调整。下面来分别讨论插入遇到的几种情况，为了方便描述，把父节点的父节点称为爷爷节点，和父节点有共同父节点的称为叔叔节点。插入之后主要涉及涂色和旋转，这里只讨论插入节点的父节点是它爷爷的左子节点的情况，如果是右子节点就不再介绍，因为原理都一样，只是左旋和右旋的区别。

（1）如果插入的是根节点。

如果插入的是根节点，直接把它涂黑，然后返回即可。

（2）如果插入节点的父节点是黑色。

如果插入节点的父节点是黑色，但插入的节点是红色，没有破坏任何一条性质，不需要做任何调整。

（3）如果插入节点的父节点是红色，叔叔节点也是红色。

因为插入的节点是红色，而父节点也是红色，所以破坏了性质4，需要把父节点涂成黑色。因为父节点之前是红色的，所以它肯定不是根节点，所以插入的节点肯定有爷爷节点，并且爷爷节点一定是黑色的。把父节点涂成黑色之后，经过父节点的这条路径就多了一个黑色节点，根据性质5，需要把爷爷节点涂成红色，但这样叔叔节点这条路径上少了一个黑色节点，所以还需要把叔叔节点涂成黑色。如果爷爷节点是根节点，还需要把它涂成黑色（根节点是黑色的），否则爷爷的父节点如果也是红色，就破坏了性质4，需要继续往上判断，如图1-39所示。

总结：把父节点和叔叔节点涂成黑色，把爷爷节点涂成红色，继续往上判断爷爷节点。

（4）如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点。

这种情况下也是先把父节点涂成黑色，因为父节点变成黑色的之后，经过父节点的这条路径上多了一个黑色节点，所以还需要把爷爷节点涂成红色。那么这里有个疑问，叔叔节点该怎样处理？有的读者可能会说像前面介绍的情况（如果插入节点的父节点是红色，叔叔节点也是红色）那样把叔叔节点也涂成黑色就可以了。其实这样是不行的，主要有两点，第一：如果叔叔节点是空的怎么办，因为根据性质3，空节点也是黑色的，所以这样就没法涂了。第二：如果叔叔节点不是空的，那么它就是从前面介绍的情况（如果插入节点的父节点是红色，叔叔节点也是红色）转换过来的（涂完之后会继续往上判断），这种情况下其本来就是黑色的，再把它涂成黑色相当于没涂。既然不能改变叔叔节点的颜色，那么叔叔节点这条路径就比父节点这条路径少了一个黑色节点（因为爷爷节点变红了，叔叔节点这条路径就少了一个黑色的），唯一的解决方式就是对爷爷节点进行右旋，让父节点成为这棵子树的根节点，那么这个父节点黑色的个数就可以被它的两棵子树共享了，如图1-40所示。

总结：父节点涂黑，爷爷节点涂红，对爷爷节点右旋，因为父节点已经变黑了，就不再继续判断。

（5）如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的右子节点。

这种情况下和“如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点”中讲的类似，如果对爷爷节点右旋，会导致一条路径缺少了一个黑色节点，如图1-41所示。注意这里大家可能会有疑惑，插入的X节点怎么会有子节点？实际上这里的X节点有可能是插入的，也有可能是（如果插入节点的父节点是红色，叔叔节点也是红色）往上调整得到的，所以要放在一起看。

很明显直接对爷爷节点旋转是不行的，那么该怎么办呢？其实可以对X的父节点进行左旋，就变成“如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点”中介绍的那样了，后面按照“如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点”中的那样处理即可，如图1-42所示。

总结：让X节点指向父节点，对X节点左旋，后面参照“如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点”。

（6）如果插入节点的父节点是红色，父节点是爷爷节点的右子节点。

这里也分几种情况，和上面类似，只不过是左旋和右旋的区别，这里就不再介绍。最后来看一下代码。

2. 红黑树的删除

删除操作可以参考AVL树的删除，我们也可以看一下，这是红黑树TreeMap中的源码。

如果p有两个子节点，删除的时候不是直接删除p节点，而是用p的后继节点来替换p节点，然后删除p的后继节点。所以删除的节点要么是叶子节点，要么只有一个子节点，不可能有两个子节点。我们看到上面的代码中，如果p（这里的p已经被替换了）是叶子节点，并且是黑色，则先调整p节点，然后删除，如果不是叶子节点，则先删除p节点，然后调整replacement，为什么不是调整完之后再删除呢？这是因为删除调整的节点必须是黑色的，如果p不是叶子节点，它就只能有一个子节点replacement，根据红黑树性质，这个子节点必定是红色的，如果先把p节点删除，调整replacement节点的时候，直接把它变成黑色，不需要做任何其他变色和旋转操作，简单省事。

fixAfterDeletion函数到底是调整p节点还是调整p的子节点，我们不需要管，只需要记住在调整的这个节点的路径上少了一个黑色节点即可，大家可以自己看，这里就不逐步分析了。

1.6.4 字典树

字典树又称为Trie树、单词查找树、前缀树，也是一种树状结构，它主要利用字符串的公共前缀来减少查询次数，最大限度地减少字符串比较，比如要查找一个字符串是否存在，或者是否存在×××开头的字符串。假设字符串只包含小写字母，那么可以把字典树看作是一棵（每个节点最多有26个子节点的）树。字典树中的根节点是不存储数据的，除了根节点以外，每个节点代表一个字符，从根节点到某一节点，将路径上经过的字符连接起来，为该节点对应的字符串。比如有wang、yi、bo、yibo等字符串，只需要把它添加到字典树中，然后在每个字符串末尾标记为一个完整的字符串即可，如图1-43所示。

比如查找wan，因为字母n在字典树中没有标记，所以wan不是一个完整的字符串。在字典树中每个节点只需要两个变量，一个是记录子节点的数组，另一个是标记从根节点到当前节点为止，是否是一个完整的字符串。

这里我们规定只查询小写字母，当然如果包含其他字母，可以使用Map。

字典树的常见操作包括插入和查询，一般查询是否是一个完整的字符串，或者查询是否有某个字符串的前缀，或者查询字符串的数量，或者查询某个字符串前缀的数量，但也有删除，删除比较少见。这里不讲那么复杂，只讲简单的插入、字符串查询和前缀查询。对于其他的操作，还需要在每个节点添加一个变量，计算当前节点出现的次数即可。对于删除来说，必须先判断要删除的字符串存在，才能执行删除操作。

1. 字典树的插入

先来看一下字典树的插入，它的原理就是沿着一条路径往下插入字符，如果路径上对应的节点存在，就继续往下判断下一个字符，如果不存在，就创建对应的节点，当字符串插入完之后，把它标记为完整的字符串，也就是说，从根节点到我们标记的那个字符连接起来就是一个完整的字符串，如图1-44所示。

2. 字典树的查询

这里有两种查询，一种是查询前缀是否存在，另一种是查询字符串是否存在，原理比较简单，我们直接看一下代码。

1.6.5 哈夫曼树

哈夫曼树（Huffman Tree），也叫作霍夫曼树，或者赫夫曼树，又称为最优树，学习哈夫曼树之前，先了解几个概念。

路径：从任一个节点往下到达其他节点之间的通路。

路径长度：路径中线段的个数。

节点的权：节点的值。

节点的带权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积。

树的带权路径长度：所有叶子节点的带权路径长度之和。

在讲解哈夫曼树之前，来看这样一个问题，我们都知道现在有个词叫作大数据杀熟，也就是说用户在某一个平台消费越多，折扣就越少，消费越少折扣越多，而平台根据消费情况，把用户分成5个等级，等级从高到低分别为：贵宾卡＞豪卡＞金卡＞银卡＞铜卡。也就是说用户消费越低等级就越高，优惠力度就越大。

每次消费的时候，平台会根据用户以往的消费金额来判断是什么级别的用户，然后给用户什么样的优惠额度，如图1-45所示，每次都这样查询。后来平台发现用户的消费金额小于1000的只有1%，如果每次先判断是否小于1000，很明显大多数情况下是无效的。为了减少判断次数，最有效的查询方式就是用户最多的离根节点越近。假设消费金额在5000～20000的有40%，消费金额在20000～50000的有45%，这两类用户占85%了，这种情况下可以像图1-46中这样查询。

这里的百分比就相当于叶子节点的权值，假设用它构造一棵二叉树，这棵二叉树可以有多种，其中带权路径长度最小的就是最优树，也就是哈夫曼树。哈夫曼树就是给定n个权值作为叶子节点，构造一棵二叉树，使该树的带权路径长度达到最小。树的带权路径长度WPL(Weighted Path Length of Tree)可以记为WPL=(W1∗L1+W2∗L2+W3∗L3+…+Wn∗Ln)，其中W？表示节点的权值，L？表示从根节点到该节点的路径长度。要想让WP L最小，权值最大的节点要离根节点最近。如图1-47所示，图中展示的是用权值9，3，2，8构造的两棵树。

1. 哈夫曼树的构造

哈夫曼树的构造原则是权值越大离根节点越近，权值越小离根节点越远。哈夫曼树的构造使用的是贪心算法，如图1-48所示，它的步骤如下：

（1）用给定的n个权值创建n棵只有一个节点的树，把它们添加到集合S中。

（2）每次从集合S中取出两棵权值最小的子树，组成一棵新的二叉树，该树的权值为它的两个子树的权值之和，然后把这棵树添加到集合S中。

（3）重复步骤（2），直到集合中只有一棵树为止，这棵树就是哈夫曼树。

因为每次都是选择两棵子树合并成一棵，所以哈夫曼树只有度为0和2的节点，没有度为1的节点，也就是说哈夫曼树中每个节点要么没有子节点，要么有两个子节点，不可能只有一个子节点。一棵有n个叶子节点的哈夫曼树总共有2∗n-1个节点。每次从集合中取出权值最小的两棵树，可以使用最小堆，来看一下代码。

2. 哈夫曼编码

哈夫曼树的最大用处就是哈夫曼编码，它是一种用于无损数据压缩的权编码算法。比起定长的ASCII编码来说，哈夫曼编码能节省很多空间，尤其是对于重复率比较高的字符数据。比如一个字符串有67个字母，其中有50个字母a，2个字母b，5个字母c，10个字母d。如果使用定长的比特来表示它们，那么每个字母至少需要2个比特，总共需要67∗2=134个比特。

来看一下使用哈夫曼编码需要多少比特。看之前需要构建哈夫曼树，每个字母的个数相当于该字母的权值，如图1-49所示，构建之后规定哈夫曼树中左分支为0，右分支为1，从根节点到每个叶节点路径上由0和1组成的序列，就是该叶子节点对应字符的编码。比如a是根节点的右分支，所以它是1，c从根节点往下是左左右，所以是001，可以这样表示。

通过计算发现它们需要的比特是91，比定长的比特134少，节省了不少空间。值得一提的是，在一个哈夫曼树编码中，不会出现某个编码是另一个编码的前缀。什么意思呢？比如选择001表示a，00表示b，1表示3，当出现001的时候它是表示a还是表示bc？我们没法确定，但哈夫曼编码不会出现这种情况，因为在哈夫曼树中，每个字母对应的节点都是叶子节点，而它们对应的二进制码是由根节点到各自节点的路径所决定的，正因为它们都是叶子节点，所以每个节点的路径不可能是其他节点路径的前缀。来看一下哈夫曼树的节点类。

来看一下哈夫曼树的创建，和前面讲的类似，只不过这里多了统计字符串频率的步骤。

接着来看哈夫曼树的编码和解码。

关于哈夫曼树的解码笔者列出了两种方式，大家选择其中的一种即可，我们来测试一下。

看一下运行结果：

1.6.6 线段树

假设需要频繁求数组的区间和，可能会想到树状数组，或者是前缀和，如果是求区间的最大值或者区间最小值呢？很明显，使用树状数组或者前缀和是无能为力了，但可以使用另外一种数据结构——线段树。

线段树是一棵平衡的二叉搜索树，它将每个长度大于1的区间划分为左右两个区间递归求解。如果整个区间的长度为n，则线段树有n个叶子节点，每个叶子节点代表一个单位区间，每个内部节点可以直接获取区间的值（最大值、最小值、区间和等）。线段树是建立在线段的基础上，每个节点都代表了一条线段[a,b]，在叶子节点中a==b，对于非叶子节点，它的左子节点区间为[a,(a+b)/2]，右子节点区间为[(a+b)/2+1,b]。在前面讲树状数组的时候，提到了树状数组可以进行区间的修改及查询，但树状数组主要用于区间的求和，功能比较单一，而线段树不但能用于区间的求和，还能用于区间求最大值、最小值、最大公约数等。

能用于线段树的两个子节点的结果必须能合并，比如求和以及求最大值等，区间和=左子节点和+右子节点和，区间最大值=max(左子节点的最大值，右子节点的最大值)。如果不能合并，是没法使用线段树的，比如求众数，左子节点的众数和右子节点的众数可能不是一个，没法合并。这里以求“区间和”为例来介绍线段树，求区间的最大值和最小值原理基本一样，这里不再介绍。假设有一个长度为10的数组[1,2,3,4,5,6,7,8,9,10]，通过它来构建线段树，如图1-50所示。

我们看到叶子节点存储的是原数组中的值，非叶子节点存储的是区间的和。在线段树中，如果父节点的下标是i，它的左右两个子节点的下标分别为i∗2+1和i∗2+2。线段树中有两个数组，一个是原数组，一个是线段树数组。

1. 构建线段树

线段树是一棵平衡的二叉搜索树，构建的时候可以使用递归的方式。

2. 单点查询

单点查询是从线段树的根节点开始往下查询，直到叶子节点，最后叶子节点的值就是我们要查找的结果。

3. 单点修改

单点修改和单点查询类似，它是先找到叶子节点，然后进行修改，修改完之后，父节点的值也会发生变动，所以还需要往上推，更改父节点的值，一直到根节点，如图1-51所示。

我们看到子节点的值改了，父节点的值也要跟着改变。

4. 区间查询

区间查询会有下面4种情况。如果查找区间非常大，包含了节点区间，直接返回当前节点值即可。如果查找区间只在左子树，就在左子树查找；如果查找区间只在右子树，就在右子树查找，否则左右两棵子树都要查，如图1-52所示。

假设查找[2,5]区间的和，查找步骤如图1-53所示。

5. 区间修改

区间修改可以参考单点修改，一直往下找到叶子节点，把它的值修改一下，然后还要一直往上修改父节点值。区间修改不同于单点修改的地方在于（区间修改）可能两个子节点都要修改，就像区间查询一样。

6. 懒标记

我们看到区间修改的时候，会把每一个叶子节点都进行修改，然后往上更新父节点，但实际上可以不这样做，如果某棵子树的值全部要修改，只需要更改这棵子树的根节点即可，给它加个标记，然后这棵子树的子节点都不需要修改了。就像过年别人给你压岁钱一样，这笔钱不是直接给你，而是先给你的家长，然后你的家长再给你。由于给的人太多（类似于区间的频繁修改），你的家长说这笔钱就不逐一发给你们了，放我这保管，需要的时候再给你们。

假设需要给区间[3,9]中的所有元素加上10，当我们找到需要更新的节点区间[3,4]和[5,9]的时候，只需要修改它们的值就可以了，然后给它加个懒标记值，它们的子节点就不再修改了，但它们的父节点还是要更新，如图1-54所示。

假如需要查询区间[3,7]，首先它会在[0,4]和[5,9]两个子节点中查找，节点[0,4]又会在节点[3,4]查找，而[3,7]区间包含[3,4]区间，可以直接返回区间[3,4]的值。而[3,7]区间不全部包含[5,9]区间，所以会到节点[5,9]的子节点去找，因为节点[5,9]有懒标记，所以在到子节点查找之前，懒标记必须下发到子节点，代码中因此多了一个懒标记数组lazy。

我们来看一下懒标记下发的代码，这里是区间求和，所以需要对左右子节点的个数进行累加，如果是求最大值就不需要。

再来看一下有懒标记的区间更新，当区间被完全覆盖的时候，就不再往下走了，直接在当前节点上改，然后加上懒标记值。

再来看一下有懒标记的区间查询。

7. 动态开点

线段树虽然是一棵平衡的二叉搜索树，但创建的时候并没有看到它的节点类，因为我们使用的是纯数组trees，类似于堆，但又不同于堆，因为堆可以看作是一棵完全二叉树，但线段树不是。这就导致了trees的长度是原数组长度的4倍，其中有很多空间是没有存储的。有的读者可能会说，既然没有存储，为何还要申请那么大的空间，这里就来讲一下线段树数组trees为何要申请4倍空间。比如用长度为n的数组来创建线段树，那么线段树中肯定有n个叶子节点，并且还有n-1个祖先节点（n不等于1，否则没有祖先节点），对于线段树的最后一行不一定都是完全填满的，最后一行的节点前面必须要有空间填充，极端情况下是2∗(n-2)个节点，所以总共需要4∗n-5个节点，如图1-55所示。

既然使用纯数组会造成空间的极大浪费，可以使用另外一种方式，为每个节点创建一个实体类，这样最后一层就不需要填充了。但这样还不够，还可以继续优化，如果某些节点暂时没用到，就不需要创建，只有在需要的时候才会创建，也就是动态创建节点，我们称为动态开点。只有在数据量比较大，但查询比较少的情况下，动态开点才能发挥更大作用，我们先来看一下节点类。

代码和前面使用数组的原理一样，这里就不再写了。只不过在下推pushDown的时候，如果子节点没有创建，需要先创建子节点，用下面的代码来测试一下。

运行结果如下：

如图1-56所示，也就是说创建的时候只会创建根节点，查询的时候会把从根节点到当前节点路径上的节点全部创建出来。大家也可以尝试用非递归的方式写一下线段树。

1.6.7 笛卡儿树

笛卡儿树不是特别常见的数据结构，如果熟练掌握它，对刷题也是非常有帮助的。比如有这样一道题，给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积，如图1-57所示。

此题除了使用单调栈以外，还可以使用笛卡儿树。讲此题之前来看一下什么叫作笛卡儿树。笛卡儿树是一种二叉树，它的每个节点有两个值（x，y），其中一个满足二叉搜索树，一个满足堆。也就是说笛卡儿树同时具有二叉搜索树和堆的两种特性。假设每个节点的两个值分别是元素的下标和元素的值，使用的是最小堆，笛卡儿树的构建如下：

（1）用数组中的第一个元素创建根节点。

（2）遍历数组中剩下的元素，如果当前元素比根节点小，让根节点成为当前节点的左子节点，然后当前节点成为根节点。

（3）如果当前节点比根节点大，就从根节点沿着最右边这条路径往右走，直到找到比当前节点大的节点node，也可能没找到。如果找到，就让当前节点替换node节点的位置，让node节点变成当前节点的左子节点。如果没找到，就让当前节点成为最后查找的那个节点的右子节点。

（4）重复上面步骤（2）、（3），直到元素全部遍历完成。

我们来分析一下上面的步骤，首先是第（2）步，如果新节点比根节点小，根据最小堆（元素的值满足最小堆）的性质，那么新节点一定是根节点的父节点。又因为根节点的下标比新节点小，根据二叉搜索树（元素的下标满足二叉搜索树）的性质，根节点只能是新节点的左子树。再来看第（3）步，如果新节点比根节点大，那么新节点只能往右边查找，如果往左边就不满足二叉搜索树的性质了。如果比右子节点还大，就继续往右，所以只要比右子节点大，就会一直往右。如果比右子节点小，根据最小堆的性质，新节点就会成为这个右子节点的父节点，根据二叉搜索树的性质，这个右子节点要成为新节点的左子节点（因为右子节点的下标比新节点小），如图1-58所示。

我们看到笛卡儿树的一个重要特性就是求一个元素的左右延伸区间。比如数字3，在笛卡儿树中节点3往左一直延伸的数字是5，往右一直延伸的数字是9，也就是说在原数组中从5到9之间的数字都是大于3的（不包含自己）。笛卡儿树还有一个非常重要的特性就是如果求一个区间[a,b]中的最小值，只需要找到a、b节点的最近公共祖先节点即可。比如找6和8之间的最小值，因为它们最近公共祖先节点的值是3，所以在原数组中6和8的最小值就是3。如果想求区间最大值呢？只需要在构建笛卡儿树的时候使用最大堆即可。我们看一下笛卡儿树的节点类。

再来看一下笛卡儿树的构建，构建的时候我们需要使用一个单调栈（从栈顶到栈底是递减的，栈底存储的是根节点）来存储最右边这条路径的节点，这条路径从上到下是递增的，每次查找的时候从下往上进行查找，也就是从栈顶元素开始比较，比新节点大的都要出栈，最后要记得把新节点入栈。

我们再来看一下开始讲的那道题，把它转换为笛卡儿树，前面说过笛卡儿树的一个重要特性就是求一个元素的左右延伸区间，我们只要计算每一个节点的左右延伸长度，然后计算它的面积即可，左右延伸的长度就是矩形的宽，当前节点的值就是矩形的高。怎样求左右延伸的长度呢？其实仔细观察就会发现，这个长度就是以当前节点为子树的节点个数。通过后序遍历的方式从下往上遍历每一个节点，就可以计算每一棵子树中节点的个数，最后看一下代码。

1.6.8 其他树

关于树的种类非常多，除了书中介绍的以外，还有很多，比如B树、2-3树、四叉树、八叉树，散列树、伸展树、Treap树等。剩下的就不在书中逐一介绍了，如果大家有兴趣，可以自己研究。