【算法】为什么到处都是树

导语

车窗外，路两旁，整整齐齐的是身姿各异的树；会议室，小黑板，不经意间出现树状的结构图；揉了揉眼睛，终于看完一篇和树相关的算法，突然涌现起当年上数据结构课时相同的瞌睡感。迷迷糊糊间，一颗颗树出现在眼前，脑海中回响着一个问题：为什么到处都是树啊？

我们身边到处都是树

是的，我们身边有很多树。在公园、在小树林、在小道边，我们都可以看到各种各样的树。它们形状各异，却又都有着相同的特征，譬如都有根、有枝和有叶。

路边随处可见的树

自然界中有很多树，这是很自然的事情。而人类习惯于从自然中得到启发，于是很自然的，人们开始使用树来表示知识。比如，族谱，比如，八卦。

使用树来表示知识

不止于知识的表示，树还成为了我们的日常思维工具。例如金字塔思维、逻辑树和思维导图，它们都是一颗颗树。

树已经成为我们常用的思维工具

当然，在人类创造的非自然产物——计算机中，存在着更多的树。例如目录、HTML和DNS域名服务等等，都是以树的形式组织。

计算机中普遍存在的树

在计算机的世界里，还有我们熟知的树相关的数据结构和算法。它们存在于计算机的各种应用场景中。从计算机中的数据表示、压缩、存储及索引，再到机器学习算法，树都占据重要地位。例如我们熟知的外存索引使用的B+树，频繁项挖掘使用到的FP树，以及分类使用到的决策树等等。

各种应用场景中可见树的身影

是的，计算机中也到处都是树。但为什么到处都是树？我难以寻得答案，只能抽取出几颗树来，看能不能从中看出些端倪。也寄希望于各位读者，能够赐予我一个满意的答案。

答案的寻找

B+树

我们经常使用的外存索引，例如Mysql中的索引，使用到的就是B+树。因为大型数据的存储，查询瓶颈在于磁盘I/O的访问次数。磁盘I/O访问过于频繁，就会导致查询效率低下。而B+树这种多叉平衡查找树，好处是一个节点就能包含很多个值，从而大大降低树的高度，减少了磁盘I/O的访问，提升了查询效率。这里我们可以看到，树节点的空间划分能力（这里是一维空间）提升了查询效率。

R树

R树把B+树(一维空间)的思想很好的扩展到了多维空间。R树的核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外接矩形，这个最小外接矩形就成为上一层的一个节点。如果查询的位置不在当前节点表示的矩阵范围内，那么也不可能在其子节点所表示的范围内，大概就是这么个思想。这里可以看到，R树同样是利用树节点具有的空间划分能力优化了查询性能，而且更直观地表达出上层节点包含了子节点范围的含义。

R树

KD树

虽然已经说了R树，但还是要提一下KD树。因为KD树很好地表达了兄弟节点具有某种意义上的相似性这层含义。如果我们想要在一堆数据点中找到和某个数据点p(x, y)最相近的n个点，我们通常的做法是计算所有的数据点与p点的距离，然后返回距离最小的前n个。但是这样做的效率并不高。KD树通过把整个空间进行分割并以树状结构进行记录，我们只需要在问题点附近的一些区域进行搜寻便可以找到最近的数据点，节省了大量的计算。除了划分空间的能力，这里还可以看出树的另一个优势，即是树状结构能保存局部性的信息，相邻的兄弟节点具有某种属性的相近性。

KD树

决策树

树在机器学习中占据着十分重要的地位，决策树便是最耀眼的那棵树。决策树表现和代码的IF-ELSE一样，区别在于决策树是数据驱动自动生成的。每个节点在选择某个属性去划分数据的时候，使用某种评判标准（信息增益和基尼系数等）去做属性列的挑选，最终将无序的数据变得更加有序，从而生成一颗分类（或回归）树。

同样是空间划分，但可以看到划分的标准是可以多种多样的，意味着树存在着更多的扩展变化能力。而且树的构造简单及直观的表达能力，要优于很多很多黑盒子算法。

决策树

孤立森林

孤立森林有多颗孤立树构成，用于快速检测异常，如检测设备异常、网络攻击及交易欺诈等。孤立树的构造方法很简单，通过从样本中随机选取属性列及属性列的值将样本数据不断划分，直至节点不可分。其主要思想是：异常点分布稀疏且离密度高的正常群体较远，容易快速被孤立出来。在树中表现为深度较小的叶子节点，如图中的节点d。

孤立树

还是利用了树的空间划分能力，但这里的划分是随机地划分，借由样本的分布把异常点提前分割出来。比较有意思的是，它可以很直观地通过叶子深度来表示稀疏点。

哈夫曼树

说到利用树形的特征，这里还得提一下哈夫曼树。哈夫曼树的定义是：将具有权值（节点占整体的百分比）的n个叶子节点，构造一颗二叉树，当这棵树的带权路径长度（节点的权值与路径长度的乘积）达到最小，则称为哈夫曼树。如下图c为构造的哈夫曼树。主要思想：使用不定长编码来压缩数据，出现频率高的字符对应的编码短，出现频率低的字符编码相对长，从而使数据长度变短。

哈夫曼树

这里也是利用树形的特性。叶子到根路径唯一，可被用于编码；叶子深度可表示权值。

FT-TREE

FT-tree 是一种扩展的前缀树结构，用以表示交换机系统日志消息模板。FT-tree的基本思想是，系统日志消息中详细信息字段的子类型通常是频繁出现的单词的最长组合。因此，提取模板等价于从系统日志消息中识别出频繁出现单词的最长组合。

FT树

构造类似FT-TREE，频繁项挖掘使用到的FP-TREE也是一棵树，只是使用树得到频繁项的方式有所不同。它们都同样地用到了树的一个性质，就是兄弟节点共享相同的祖先。

蒙特卡罗树搜索

蒙特卡罗树搜索是一种搜索最优决策的方法，它结合了随机模拟的一般性和树搜索的准确性。如下图所示，蒙特卡洛树搜索一般分为选择、扩展、模拟及反向传播四个步骤。这似乎很符合我们下棋的思维习惯：选择一个看似不错的位置，假设在此落子，推算后序的走势，发现大规律会输，再重新选择一个位置推算。树恰恰能表示这种决策过程，因为它有宽度，能表示多个选择；同时它也有深度，能表示推算的深度；而父节点，则可以用来统计后序推算的胜率。这样想来，使用树是那么的理所当然。

蒙特卡罗树搜索

我的答案

写到这，我已经快忘了自己在哪里了。只依稀记得，有很多树，能从中看出一些有趣的特性。树的划分空间的能力，既有用于提升查询性能的，又有用于数据分类的，得益于划分规则的可扩展性。树的特性，比如树根唯一，所有有了堆排序；比如叶子到根的路径唯一，所以可以用于表示编码；比如兄弟节点共享祖先，所以有了前缀树；比如兄弟节点间距离相近，所以可以快速找出临近点……

人的思维是发散的，非线性的，正如之前提到过的思维导图之类的思维工具一样，和树的结构是相似的。而在处理非线性问题时，人便想到了树。所以用于处理问题的计算机中，便出现了树。也因为树的直观、性能优越以及可扩展性，树得到了更广泛的使用。所以才会导致处处都是树的现象。

这便是我所以为寻得的答案。你觉得呢？