心中有“树”！图文并茂介绍数据结构中常见的树（三）

共 4833字，需浏览 10分钟

· 2021-12-01

在前面两篇文章中，我们简要介绍了数据结构中的各种【树】在搜索、数据库等领域的使用场景，希望对大家有所帮助。

本篇内容，是我们 《心中有“树”》 系列的最后一篇，我会在这里继续给大家介绍一些树的结构和应用场景，也会跟大家分享一下我个人对这些“杂七杂八”的知识的想法和态度。

大家好，我是不会写代码的纯序员——Chunel Feng，很高兴又在这里跟各位绅士见面了。上一章内容中，我们跟大家介绍了【树】结构在编码、缓存、数据库等方面的应用例子，包括了哈夫曼树、最小生成树、线段树、伸展树、B/B+树、LSM 树。这一章，我们再继续这个话题，聊一聊“树”在相似搜索、人工智能等领域的一些常见应用。

相似搜索领域

相似搜索（ANN，Approximate Nearest Neighbor）技术又叫做“向量检索技术”或“相似最近邻搜索技术”，指的是单个向量在海量向量中，通过预先设定的索引结构，快速查询出距离（如：欧氏距离、曼哈顿距离等）相近的 TopK 个向量的方法。该技术被广泛应用于以图搜图，智能问答，搜索推荐系统等领域。

常见的使用场景嘛，比如将海量图片通过 embedding 技术，生成对应的海量向量集合（Dataset）。然后将查询图片通过同样的方法，得到一个向量（query point），并在 Dataset 中找到距离最近的 n 个向量，就可以粗略认定：这 n 个向量对应的图片，和查询图片比较相似。

K 维树（K-Dimension Tree）

我们之前聊过很多树，有的节点中包含一个信息（如：红黑树），有的节点中包含多个信息（如：B 树）。还有一种情况，树中的每个节点中，包含一组信息——一个高维向量。这个概念就迎合了上面提到的向量检索了。

KD 树是早期做向量检索的方案，建树的时候通过空间内点的方差来确定切分方向、进而再确定出切分点和切分平面，并以此方式递归的对海量向量数据进行切分，直至形成一颗树形结构。

看上面这张图，[2,3] [5,4] [4,7] [7,2] [8,1] [9,6]这几个二维向量，就被以切面（左图中红色和蓝色的线）分割的形式，放在了右图的 KD 树中。查询的时候，根据 KD 树的路径中的切点和切面信息，通过对比寻址和回溯等流程，最终在海量向量数据中，在减少比对次数的基础上，找到与 query point 邻近的 TopK 个点，从而达到较少查询耗时的目的。

Annoy 树

Annoy（Approximate Nearest Neighbors Oh Yeah）算法是 Spotify 公司开源出来的算法名称，目的和 KD Tree 一样，也是为了解决海量高维向量的相似搜索的问题。其中也用到的树的思路，而且是多棵树组成的森林。

跟 KD 树不同的是，它切分的方式是通过对海量向量集合做随机点开始的二值聚类，然后将聚类的索引信息放到根节点的左右两侧（作为“簇”），然后以此方式继续递归，直到每个簇中的节点数量小于特定值为止。这样下来，除了叶子结点以外，所有的路径结点中实际上存储的只是切面的信息，而所有的向量信息均存放在叶子结点中。

这种骚操作是不是有点熟悉，KD 树和 Annoy 树的关系，是不是有点像 B 树和 B+树的关系。需要说明的是，Annoy 算法选择起点的时候有一定的随机性，相同的向量集用同样的方法反复多次是会产生不同的 Annoy 树的。这些树又共同组成了一个描述这批海量向量数据集合的森林。这样做，是为了可以通过多次查询并合并/去重查询结果的方式，提高最终结果的准确率。

类似的技术，还有随机投影树（Random Projection Tree），不过在做平面切分的时候，跟 Annoy 有所区别。有兴趣的朋友可以深入了解一下，这也是一种通过树（森林）的方式，解决 Ann 问题的思路。

注：目前在相似搜索领域，基于图的算法无论在召回率还是查询耗时层面，都有一定的优势，因此也相对更为主流。但是森林结构有天然的并行属性（因为有多棵不同的树嘛），这是单纯的图结构所不具备的。因而个人认为这个细分领域，今后可能往【图+树】的方向发展。

人工智能领域

决策树 (Decision Tree)

决策树是一种基于树型结构的、可解释的、有监督的机器学习的方法，而非单纯的指一种结构。决策树中的每个非叶子节点均表示一个属性上的判断，而每个叶子结点表示一种分类结果。整体上描述的是算法为了达到特定目标，根据一定的条件而进行选择的过程，被用于机器学习中的分类任务。

看上面这张图，描述的就是：根据【是否拥有房产】【是否已婚】【年收入是否超过 80（元，嘿嘿，我过了）】这三个（在非叶子节点中）条件来判断借贷人是否有偿还能力（结果在叶子节点中）的一颗决策树。比如，一个没有房产、未婚、年薪低于 80 的人，会如图中蓝色箭头所示，被判定为无偿还能力。

至于这几个条件中，哪个条件应该被先判断（在树相对顶部的位置），大家可以自行了解一下 ID3、C4.5、熵减、信息增益啥的。决策树有着天然的可解释性，在推荐系统中有着广泛应用，有兴趣的朋友还可以了解一下 GBDT（Gradient Boosting Decision Tree，渐进残差决策树），这也属于森林的概念了。

蒙特卡洛树（Monte Carlo Tree）

蒙特卡洛是摩纳哥一个著名赌城的名字，蒙特卡洛树和游戏、赌（和谐）博等领域能扯上一些关系，常被用于博弈游戏中推测胜出的概率。前阵子大火的 AlphaGo，其中就用到的了蒙特卡洛树。

它主要描述的是，通过在设定范围（比如：游戏规则、单步计算耗时等）内，大量反复执行 选择（Selection）、扩展 (expansion)、模拟（Simulation）、回溯（Backpropagation) 这四个流程，逐步的构造出包含了各种可能执行路径，及其对应节点胜出概率的树型结构。

蒙特卡洛树的路径中的每个节点，都表示从当前状态继续进行，可能胜出的概率。而任意节点的子节点，就表示从当前状态出发，至少有几种可选的方案（拿象棋来说吧，就表示，此时可以“把炮向前走三步”、或者“把卒向前走一步”等）。对应到上面的图，可以理解为，经过一系列骚操作后，根节点出发（针对象棋，就理解是当头炮吧），胜出的概率由 12/21 变化为 12/22，从而变的更接近实际情况了。

我们刚才聊到了曼哈顿距离、蒙特卡洛树，这些都是以外国城市命名的知识点。于是，我就去搜索了一下有没有什么内容是以中国的城市命名的。最后，我学到了一些地产和航空航天方面的知识，比如：蚌埠住了，芜湖起飞。

再简单介绍几种其他领域中常用到的树吧。

默克尔树（Merkle Tree）

默克尔树又叫做哈希树（Hash Tree），它是将整体内容分成多个区块，然后逐层合并计算哈希值，并且放入树的父节点上的结构。相比于将对分块的哈希值，统一记录到一个 Hash Table 的做法，默克尔树的主要优势，是它可以分部分进行校验，常用与区块链，密码学等领域。

看上面这张图吧，我们可以认为 L1(假想为是一个大文件的一个分块)对应的哈希值[Hash 0-0]，L2 对应的哈希值是[Hash 0-1]，而[Hash 0]是对上述两个哈希值（不是分块）再进行哈希后得到的值。这样，在下载文件的时候，如果我想确认前半部分有没有下载完毕，我直接判断已下载部分的[Hash 0]值，跟预期是否一致即可。

当然了，真实的使用场景可能比这复杂了很多。以上说法也是站在一个区块链技术门外汉的角度的进行描述。如果我真的很懂的话，也许我买的币也不会亏那么多了，呜呜。

矩形树（Rectangle Tree）

R 树也被叫做空间索引树，可以简单理解为是 B/B+树的高阶版本。它的核心思想是通过最小外接矩形的形式，逐层聚合（空间）距离相近的节点。主要应用于地理位置查询等领域，比如在地图上找餐厅这类问题，也被用于数据库领域。

上图是一个二维的 R 树。图中有 10 个小分块（可以理解成是餐厅、酒店、娱乐场所等），分别是 A~J。它们在 R 树上根据所在位置，被用绿色的矩形分成了 4 个部分——分别为 P1/P2/P3/P4。如果需要查询红色实心方框附近的娱乐场所，通过在 R 树上的映射可知，仅搜索 P3 和 P4 对应的分块即可，从而减少了查询范围。

相关的内容还有 R*树、R+树、Hilbert R 树等。有兴趣的朋友可以继续深入研究。

本章小节

这篇文章是树系列的最后一篇，很高兴能在您的陪伴下，一直走到这里。在这几篇文章中，我把我所了解的 Tree 相关的内容都罗列了一遍，也介绍了这些结构的使用场景和解决的问题。其实，我个人在日常工作中，用到的这方面的知识也不多，像“默克尔树”这种，我也都是最近刚了解的——但，这在某些特定细分领域中，是最最基本的知识。

这个系列的内容，每一个小节都比较短，也比较浅，希望大家都能看懂并有所收获。今后，如果在特定行业用到了其中某些部分，还需要大家深入了解该结构和其周边的相关知识。毕竟对细分领域知识点了解的深度，才是区别【新手】和【专家】的评判标准。如果，各位专家发现我的表述中，有什么错误、或者不合理、不清楚的地方，也希望不吝赐教。

又想到几年前，我为了找工作，猛刷过一阵子 Leetcode。其中很喜欢写的就是树相关的题目——因为简单啊，代码量一般不多，有思路的时候写起来很顺手的。这几年，因为工作原因吧，很久不练，偶尔想写两题的时候，都发现已经很生疏了。

但也是随着工作经验的增长，相比于之前单纯的为了快速写出某个题目的双优解法，我会更愿意去关注和思考一些题目对应的数据结构和算法知识点的背后所隐射的内容，比如：

•它常被用于什么场景？•它能解决我当前的什么痛点？•它能给我接下来的工作，带来怎样的变化？•它还和哪些知识点有关，互相对比有何优劣。能否结合使用，或取长补短？•结合手头的任务，我还可以如何去定向的改造和优化它？

诚然，数据结构和算法的思路，对任何一个程序员来说，都至关重要。但大家也不用仅仅为了应付一些公司面试，成为“小镇做题家”吧。必须承认，当前行业环境下，很多人的日常工作中，是基本是用不到这些知识的。如果真的用到了，那落地的过程一定比题目中描述的情况，复杂百倍。双优的题解和答案，总是可以很简单的在网上找到，但“学有所思”、“学以致用”的能力，更应该是我们在工作和成长的过程中，一点点积攒和沉淀的财富。

我是 Chunel Feng——是一个不会写代码的纯序员。感谢您的关注，欢迎添加我的个人微信，随时指教和交流。

GitHub：https://github.com/ChunelFeng

个人博客：http://www.chunel.cn

最后也欢迎大家关注 Doocs 公众号，加入 Doocs 开源社区，这是一个优质的以交流分享算法和后端知识为主的技术型开源社区。在其中，你可以结识很多大佬，学到很多新知识，增长见识；也可以做出自己的贡献，去帮助需要的朋友。希望我们能一起，用自己的所见、所学和所感，让世界变得更美好——哪怕只有一点点点点点点！