数据结构中常见的树

ittbank 2023-05-29 17:56

TI MCU方案：能源基础设施实时控制 如何增强能源基础设施的实时控制？

哈夫曼树(Huffman Tree)

哈夫曼树，又被称为最优二叉树，属于带权值二叉树的一种。它的真实节点全部分布在叶子节点中，是各种可能的组合中 WPL 值最小的形式。组合形式可能不唯一，但 WPL 值一定为最小。

介绍一下 WPL（Weighted Path Length），也就是带权路径长度，说简单一些就是【节点到根节点的路径长度 * 该节点的权值】。说白了就是权值越大的节点，离根节点越近就对了。

WPL_A = 9x2+4x2+5x2+2x2 = 40
WPL_B = 9x1+5x2+4x3+2x3 = 37
WPL_C = 4x1+2x2+5x3+9x3 = 50

看一下上面这张图和三个对应的 WPL 的值，很明显可以看出来(b)是[9，4，5，2]这几个节点对应的哈夫曼树（的一种表现形式）。我们刚才也提了，哈夫曼树组成的形式可能不唯一，就比如说把(b)镜像过来看，也是哈夫曼树。

哈夫曼树的应用中，最有名的就是哈夫曼编码了。通过这种编码方式，可以使得整体编码的长度最短。还需要说明的是，它是一种前缀编码，任何一个编码值，都不会为其他编码值的前缀（最左子串）。

在 NLP(自然语言处理)领域划时代之作—— word2vec 的过程中，也通过哈夫曼树结构来加速查询高频词语，有兴趣的朋友可以了解一下。

最小生成树(Minimum Spanning Tree)

最小生成树，虽然叫做“树”，但是它更多地出现在“图”相关的知识中，描述的是将一个有权图，转化成所有节点均可连通，并且连接两边的权值之和最小的树形结构。提到这个，就肯定要说一下大名鼎鼎的 Prim 算法和 Kruskal 算法，这两种算法分别是从随机顶点的角度和权值最小的边的角度出发，一步一步地选出适合的边，然后最终形成一颗包含全部 n 个节点和 n-1 条边的最小生成树。

这方面比较经典的应用，就比如多个城市之间建铁路，要求每个城市都连通、并且铁路距离总和最小这种问题。后来我想想，送外卖的时候兴许也能用到这个方法，该为 35 岁之后的职业生涯提前规划起来了。

线段树(Segment Tree)

线段树，是一种特殊的平衡二叉查找树，每个叶子节点表示一个真实的节点信息。而路径上所有的非叶子节点，用来表示它包含的各层级子节点的范围，并用于标记这个范围内的一些信息，比如范围内的 max 值或 sum 值等。

线段树可以较好地兼顾区间插入新数据和单点数据修改的逻辑。当更新叶子节点内容的时候，只要更新该节点对应路径上的节点信息即可。主要用于一些对范围查询有很高要求的场景。

值得一提的是，线段树可以通过一个一维数组来表示，如上图中绿色数字所示（其中 10、11 为空缺信息）。还需要说明的一点是，类似的概念还有区间树，也有人将这两个概念画了等号，大家自行了解分辨。

伸展树(Splay Tree)

伸展树是一颗非平衡二叉搜索树。它的设计思路是基于一种假设：最频繁被查询的信息，它（和它附近的节点）在下次查询的时候更可能被查到。所以，通过 Splay Tree 查询的时候，会随着被查询的信息，反复调整树本身的结构，从而将经常被查询到的节点，放到 root 附近。这样就可能会加速查询的效率。

这个乍一听，有点像 LRU 或者 LFU 类似的结构，但又有所不同。首先，Splay Tree 中会保留所有的节点信息，不存在过期（或超限）销毁的情况。还有一点就是它并不是被查到之后立即置顶，会有一些其他的综合考量（比如，每次最多进行两次 n 次旋转）。

看一下上面这张图吧，它模拟的是（频繁）查询 R 的时候，Splay Tree 的变化情况。说白了就是把 R 节点放到根节点的位置，下次查起来就方便多了。Splay Tree 比较适合做缓存，特别是在热点数据相对集中的情况下，查询效率很高。举个应用的例子吧：我们常用的输入法，当你输入完拼音之后，会根据你的之前的选择情况，优先出现某些词语。但很多情况下，又不会直接把你上次选择的词语直接置顶，这就可以理解为是参考了伸展树的思路（当今输入法的排序，实际更多的应该是用 AI 算法是做概率预测，而非单纯的 Splay Tree）。

数据库领域

数据库中非常核心的一个部分，就是索引结构的设计——这几乎决定了数据库的应用领域。而索引结构的设计，又是数据结构和算法的“重灾区”。下面我们就来列举几种数据库领域中，常见的树结构。

B 树

传统的二叉树中，每个节点中包含一个信息，这样如果节点数比较多，路径就会很深。路径深了，对应的问题就是查询的过程中，需要经过更多的节点，从而造成性能下降。基于此，B 树诞生了。

B 树也属于一种自然平衡树。内部通过分裂机制，能够保持数据的有序。它的单个节点中可以保存 2~4 个信息。单个节点内部有序，节点之间信息的间隔，可以作为划分下面部分的依据。

看上面这张图，树中一共有 10 个人信息，按照红黑树的形式存储，最长的路径应该是 4。而通过 B 树进行存储，就会显得“矮胖”了，对应的跨节点查询次数也就缩短了。

B 树比较适合于单点查询的场景，比较常见的应用就是 MongoDB 了。当然了，B 树也有一些不适合的场景，比如所有节点都放在磁盘上，则读写性能相对差；再比如说，如果我想查 5~9 范围内的所有数据，用 B 树是不是就需要在 3 个节点中反复横跳？

B+树

B+树就是为了解决上面抛出的两个问题而设计的。与 B 树相同的是，B+树的节点中也包含了多个信息。但相比于 B 树，B+树做了一些改动：非叶子节点中仅保留数据之间的相对关系，而所有的真实信息均包含在叶子节点中。这样的话，相对关系信息就可以放到内存中，而将所有节点信息（可以认为量较大）保留在磁盘中。

每次查询，通过相对关系，在内存中就可以快速的定位到具体的节点信息，从而减少磁盘的 IO 次数。这样做还有一个好处，可以通过一条“线”将所有叶子节点串联起来，从而方便做范围查询。大名鼎鼎的 Mysql 的存储引擎 InnoDB，使用的就是这种思路。

不知道有没有朋友跟我一样，在很长的一段时间内，把数据库索引和 B+树画上了等号。其实不然，不同应用领域的数据库，有着不同的索引结构。B+树的信息存放在磁盘中，且属于非顺序写入，所以查询性能很高，但写入的性能偏低。在大数据存储和日志服务等需要频繁写入操作的领域，就有些不合适了——这就要引出我们接下来的话题了。

日志结构化合并树（Log Structured Merge Tree）

多年前，谷歌在发大据领域发表了Big Table相关论文，LSM 树是其中的实现思路。我第一次听说 LSM Tree，是有幸跟一位 HBase 领域的资深大佬一起喝茶的时候。当时我红着脸表示，只听说过其中的一部分。