文章目录
前言
树结构是计算机科学领域中的一种优秀数据结构，在很多问题求解和应用中都有应用。目前，*把树相关的数据结构可以分为四类。本文从每一类中分别选取一种做了简单介绍。
写的我头都大了，连着肝了6h。
一、平衡多路查找树
是一种search tree
在计算机科学中，B树是一种自平衡的树型数据结构，它能保持数据的排序，并允许在对数时间内进行搜索、顺序访问、插入和删除。B树是对二元搜索树的概括，允许节点有两个以上的子节点[2]与其他自平衡二元搜索树不同，B树很适合于读写比较大的数据块的存储系统，如磁盘。它常用于数据库和文件系统中。
1.概述
1.1定义
（摘自*）
According to Knuth’s definition, a B-tree of order m is a tree which satisfies the following properties:
- Every node has at most m children.
- Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
- The root has at least two children if it is not a leaf node.
- A non-leaf node with k children contains k − 1 keys.
- All leaves appear in the same level and carry no information.
Each internal node’s keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.
B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。按照翻译，B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引，综合效率较高。又称：B-Tree、BTree、B树等。
1.2特性
- 每个结点x(假设为x)有如下属性:
- x.n，表示当前存储在结点x中的关键字个数。
- x.n的各个关键字本身：x.key1, x.key2, … 以非降序存放(升序)，使得 x.key1 ≤ x.key2 ≤ …
- x.leaf，是一个布尔值，如果x是叶子结点，则为TRUE, 如果x为内部结点，则为FALSE。
- 每个’内部结点x’还包含x.n+1个指向它的孩子的指针x.c1, x.c2, … 。 叶子结点没有孩子结点，所以他的ci属性没有定义。
- key和指针互相间隔，节点两端是指针，所以节点中指针比key多一个。
- 每个指针要么为null，要么指向另外一个节点。
- 关键字x.keyi对存储在各子树中的关键字进行分割：如果ki为任意一个存储在以x.ci为根的子树中的关键字，那么：k1 ≤ x.key1 ≤ k2 x.key2 ≤ … ≤ x.keyx.n ≤ kx.n+1.
难理解可以这么说：- 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于(key1)，其中(key1)为node的第一个key的值。
- 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于(keym)，其中(keym)为node的最后一个key的值。
- 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于(keyi+1)且大于(keyi)。
- 每个叶子结点具有相同的深度，即树的高度h
- 每个结点所包含的的关键字个数有上界和下界。用一个被称作B树的最小度数的估计整数t(t ≥ 2)来表示这些界： 除了根结点以外的每个结点必须至少有t-1个关键字。因此，除了根节点以外的每个内部结点至少有t个孩子。（因为上面说了右x.n+1个指向它的孩子的指针） 如果树非空，根结点至少有一个关键字。
每个结点最多包含2t-1个关键字。因此，一个内部节点至多可有2t个孩子。当一个结点恰好有2t-1个关键字时，称该结点是满的(full)。
2.数据结构
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）
3.关键的基本操作的具体实现概述
从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：
例如：来模拟下查找上上图所示数文件29的过程：
(1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。
【磁盘IO操作1次】
(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
(3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。
【磁盘IO操作2次】
(4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
(5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。
【磁盘IO操作3次】
(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
4.应用
鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如：
1、B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。
2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。
二、左偏树（Leftist Tree）
是一种heap
左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。（来自百度百科）
1.概述
- 左偏树是一棵二叉树，也是一种可并堆，拥有堆的性质，可以像堆一样合并。
- 左偏树顾名思义，有“左偏”的特点，既每个左子树节点的dist一定大于等于右子树节点的dist。
- 由性质2可得：t[x].d=t[t[x].ch[1]].d+1
- 同时，我们需要注意左偏树的dist并不意味着深度，跟深度无关。dist 为它到离它最近的叶子节点的距离+1，叶子节点的dist=1，空节点的dist=0
2.数据结构
左偏树是可以合并的二叉堆, 首先满足作为堆的基本性质:
- 树形结构
- 节点储存信息, 有优先级
- 每个节点的优先级大于其子节点的优先级
此外, 左偏树有一些额外的性质, 来保证它合并的效率.
左偏树的节点至少需要保存:
- 左右子树节点 lc, rc
- 该节点到 有空子节点的节点 的最短距离 h
- 优先级权值 w
有空子节点的节点, 就是指子节点数不为2的节点
除了堆的性质, 左偏树还满足 “左偏” 的性质, 这一点保证它的合并效率是O(log n)
即每个节点的左子节点的h不小于右子节点的h, 因而有 h[rt] = h[rc[rt]] + 1
下图即是一棵左偏树, 节点上即权值(优先级), 小根堆, 蓝色数字为h
(注意, 左偏树的左子树一定不小于右子树)
3.关键的基本操作的具体实现概述
3.1合并操作
3.1.1图示
以小根堆为例:
假如要合并两个堆 A, B
首先令 w[A] < w[B], 然后进行合并merge(A, B)
在该函数中:
- 如果 w[rc[A]] < w[B], merage(rc[A], B)
- 如果 w[rc[A]] > w[B], 交换 A的右子树 和 B, 然后继续merage(rc[A], B)
- 如果 A的右子树 或 B 为空, 则直接连接, 结束
如下图演示:
可以看得出来, 这一番操作后失去了左偏的性质, 所以还要在递归回溯的过程中维护左偏性质:
如果节点左子节点的h小于右子节点的h, 则交换左右子树, 维护该节点的h
3.1.2伪代码
merge返回合并之后的树根仍然以小根堆为例。
merge(A, B)
{
if(A == NULL) return B;
if(B == NULL) return A;
if(w[A] > w[B]) swap(A, B);
rc[A] = merge(rc[A], B);
/* 维护左偏性质 */
if(h[lc[A]] < h[rc[A]]) swap(lc[A], rc[A]);
/* 维护节点 A 的 h值 */
if(rc[A] == NULL) h[A] = 0;
else h[A] = h[rc[A]] + 1;
return A;
}
4.应用
4.1例题
4.1.1题意：
一群猴子，每只有战斗值，开始他们互不相识，不相识的猴子直接会打架，打完架后，他们所在的小群体都相互认识，认识之后就不会再打架了。打架时，两只猴子会分别选择自己团体里战斗值最高的一只猴子出来应战，打完架后，这两只打架的猴子的战斗力减半（比如5变成2）。
要求输出每一场架打完之后，这个团体里战斗值最大是多少。
4.1.2思路
- 每一个团体，构造一个大根堆集合。
- 每次打架时，先检查A，B是不是在一个集合中，不在的话，就从集合中删除最大的点（即根），然后把他的战斗值减半，再插回原来的集合中去。
- 然后把A，B合并，输出根的值。
三、AC自动机算法
是一种Tires的进阶
字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
1.概述
AC自动机，是Aho-Corasick automaton的简称，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。AC自动机是对字典树算法的一种延伸，是字符串中运用非常广泛的一种算法。
AC自动机在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abce和bcd,我们找到c发现下一个要找的不是e,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)
2.数据结构
2.1主要思想
AC自动机就是在KMP算法的思想上加上trie树来实现的一个适合多个模式串的匹配问题。KMP算法时间复杂度优秀的原因是有一个next数组，也叫做失配指针数组，使得匹配的时间复杂度严格O ( M + N ) O(M+N)O(M+N)，AC自动机也有这样的数组来在失配的时候去跳到相应应该去的地方。所以，AC自动机分两步：
- 建立trie树存下模式串
- 创造next失配指针
2.2建树过程
建上树
一般,fail指针的构建都是用bfs实现的。首先每个模式串的首字母肯定是指向根节点的
现在第一层bfs遍历完了,开始第二层
(根节点为第0层)第二层a的子节点为s,但是我们还是要从a-z遍历,如果不存在这个子节点我们就让他指向根节点(如下图红色的a)
当我们遍历到s的时候,由于存在s这个节点,我们就让他的fail指针指向他父亲节点(a)的fail指针指向的那个节点(根)的具有相同字母的子节点(第一层的s),也就是这样
按照相同规律构建第二层后,到了第三层的h点,还是按照上面的规则,我们找到h的父亲节点(s)fail指针指向的那个位置(第一层的s)然后指向它所指向的相同字母根->s->h的这个链的h节点,如下图
完全构造好后的树
3.关键的基本操作的具体实现概述
3.1如何建立trie树？
trie树，就是把字符串像一棵树一样的存起来的数据结构，减少了需要的空间，也减少查询的时间复杂度。
int cntN=0;//节点个数
void Insert_String(char st[]){
int len=strlen(st),now=0;
for(int i=0;i<len;i++){
if(trie[now].nxt[st[i]-'a']==0){
trie[now].nxt[st[i]-'a']=++cntN;//没有就新建一个节点
}
now=trie[now].nxt[st[i]-'a'];
}
trie[now].cnt++;//最后cnt统计单词个数
}
3.2 如何创造失配指针？
我们用BFS的形式去创造失配指针。
根节点直接连着的结点的失配指针都指向根节点。
再下面的结点，就指向父亲的fail的与其相同结点，如果父亲的fail没有与其相同的结点，当然就指向根了。
void Make_Fail(){
queue<int> q;
for(int i=0;i<kind;i++){
if(trie[root].nxt[i]){
trie[trie[root].nxt[i]].fail=0;
q.push(trie[root].nxt[i]);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<kind;i++){
if(trie[u].nxt[i]){
trie[trie[u].nxt[i]].fail=trie[trie[u].fail].nxt[i];
q.push(trie[u].nxt[i]);
}
else{
trie[u].nxt[i]=trie[trie[u].fail].nxt[i];
}
}
}
}
3.3如何匹配？
int Match(char st[]){
int len=strlen(st),now=0,res=0;
for(int i=0;i<len;i++){
now=trie[now].nxt[st[i]-'a'];
for(int t=now;t!=root && trie[t].cnt!=-1;t=trie[t].fail){
res+=trie[t].cnt;
trie[t].cnt=-1;
}
}
return res;
}
4.应用
P2536 [AHOI2005]病毒检测
这里只管匹配，只须在树上往下走，故建一只trie树即可。以母串0下标位置，trie树根节点位置起始往下搜索。
根据母串当前的字符有多种情况
- '*'被空字符串替代：trie上不走，母串走
- '*'被非空字符串替代：母串不走，trie上走，且四种方向能走的都走
- ‘?’：母串、trie都走，且四种方向能走的都走
- ‘A’‘T’‘G’‘C’:母串、trie都走
输出的答案ans先初始化为n，跑到某些字符串的end位置就减去以该节点为end的病毒串个数（当然Insert的时候就处理好了），输出ans即可。最重要的是对每个点的每个 母串上走过的位置 标记vis，不必再走过。这个优化可以把3T1M变成1个T（看来前仆后继地走一个点的情况太多了）
四、多维空间分割树（KD树）
是一种Spatial data partitioning trees
在计算机科学里，k-d树（ k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（Binary space partitioning ）的一种特殊情况。可以看到，KD树是基于欧式距离度量的。
1.概述
KD树是一种查询索引结构，广泛应用于数据库索引中。从概念的角度讲，它是一种高纬数据的快速查询结构，本文首先介绍1维数据的索引查询，然后介绍2维KD树的创建和查询
2.数据结构
KD树的算法的实现原理并不是那么好理解，主要分为树的构建和基于KD树进行最近邻的查询2个过程，后者比前者更加复杂。当然，要想实现最近点的查询，首先我们得先理解KD树的构建过程。下面是KD树节点的定义，摘自百度百科：
-
首先将数据节点坐标中的X坐标和Y坐标进行方差计算，选出其中方差大的，作为分割线的方向，就是接下来将要创建点的split值。
-
将上面的数据点按照分割方向的维度进行排序，选出其中的中位数的点作为数据矢量，就是要分割的分割点。
-
同时进行空间矢量的再次划分，要在父亲节点的空间范围内再进行子分割，就是Range变量，不理解的话，可以阅读我的代码加以理解。
-
对剩余的节点进行左侧空间和右侧空间的分割，进行左孩子和右孩子节点的分割。
-
分割的终点是最终只剩下1个数据点或一侧没有数据点的情况。
3.关键的基本操作的具体实现概述
3.1KD树构建算法：
其中的P表示待构建的元素集合，depth表示当前是KD树的第几层，如果depth是偶数，通过纵向线对集合进行划分；如果depth是奇数，通过横向线进行划分（3～5行）；第6、7行递归进行KD树中子树的构建。
算法时间复杂度为：O(nlogn)，感兴趣可以写出递推公式公式进行推到，算法导论中专门讲了这个递推公式。
3.2 KD树查询算法
如果v是叶子结点且属于区域R，则直接返回（第1行）；如果v是非叶子结点，则比较R与v的左子树lc(v)是否有交集，如果有且lc(v)完全被R覆盖，则lc(v)是所查询结果的一部分，如果不是完全覆盖，则递归查询lc(v)；对右子树也是类似的操作。算法的时间复杂度为：O(sqrt(n) + k)，其中k是最后的结果中元素的个数，其递推公式公式为：
上述算法中的二维也可升级为3维，其思维方式与从1维升级到2维一致，相应的构建算法和查询算法也与2维的一致。
4.应用
4.1例题
4.1.1题意：
平面上有n个点。现在有m次询问，每次给定一个点(px, py)和一个整数k，输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同，那么认为标号较小的点距离较大。
100%的数据中，n<=10^5, m<=10^4, 1<=k<=20，所有点(包括询问的点)的坐标满足绝对值<=10^9，n个点中任意两点坐标不同，m个询问的点的坐标在某范围内随机分布。
4.1.2思路
KD树+小根堆维护前k大。
如果堆的size没有达到k，直接插入当前点。
如果堆的size达到k且当前点大于堆顶则将堆顶弹出，将当前点插入堆。
如果堆的size达到k且子树的最大估价小于堆顶则不往下。
注意KD树往儿子走时要先走估价函数大的那一边。