后缀树

一颗后缀树是针对一个字符串而言的，该后缀树能识别这个字符串的所有后缀，能且仅能识别这个字符串的所有字串，

后缀树空间压缩

常常我们会在后缀树的边上储存字符串，而不是字符，这样可以避免大量的内存开销，每一条边，我们都记录了两个数据，字符串的起点和终点，这样就实现了后缀树的空间压缩

后缀树的构造

后缀树有很多构造算法，这里直讲最简单的，考虑一个字符串的后缀自动机，其上的paerent树便是反串的后缀树。

字典树

字典树是我接触自动机的开端，我们先讲自动机，

自动机

自动机有五个要素，开始状态，转移函数，字符集，状态集，结束状态。

自动机识别字符串

假设我们有一个自动机，他长这个样子,他能识别字符串abc.
稍等片刻！下图正在转码中

1
2
3
4

graph LR
start((start))--a--> 1((1))
1((1))--b-->2((2))
2((2))--c-->3((end))

最开始我们在位置start，也就是初始状态，当我们读入字符a的时候，经过转移函数我们到达了1号状态，如果我们在初始状态读到的是字符b，则因为初始状态没有字符b的转移函数。会导致自动机在非终结状态停机，这就意味着无法识别字符b，同理也无法识别c-z,于是在初始状态只能识别a，

然后分析状态1，只能识别b，到达状态2，只能识别c到达终态。最后就识别了字符串abc。

然后我们来考虑一个复杂一点的自动机，他能识别字符串abc、abd、bc、ac

稍等片刻！下图正在转码中

1
2
3
4
5
6
7
8

graph TB
start((start))--a--> 1((1))
1((1))--c-->10((end))
start((start))--b--> 3((3))
3((3))--c--> 10((end))
1((1))--b-->2((2))
2((2))--c-->10((end))
2((2))--d-->10((end))

如果我们不去分析其中的end节点，他的本质就是一颗树，他同时又叫做字典树，特别的，如果这个字典树的字符集为01，则他又叫做01字典树。

字典树的插入

字典树的插入应该是一个字符串，这个过程我们可以用递归实现，

字典树的删除

特别注意，为了能够支持多重集合，我们常常用一个数字来代表有多少个字符串在某个状态结束，这样删除的时候只要减少那个值就可以了

字典树的查找

递归。

递归转非递归

因为字典树的代码特别简单，我们常常直接用递归转非递归来实现。

代码

先欠着，暂时拖一个不太友好的代码在这里,这里面有一部分代码就是字典树啦。
代码链接

build

我们使用单调栈来维护树根到叶子的链，在单调栈的构建中完成树的构建

vantate point tree

vp tree 是一颗二叉树，他和kd tree有着一定的相似度,

树上信息

每一颗子树都要维护一个点集，对于每个节点，我们都维护一个距离d，然后将到该节点的距离小于d的点放到左儿子，其他的放到右儿子中。

vantate point

vantate point的选取是一个比较麻烦的事情，我们仔细想想都知道，这个点的选取肯定会影响算法，有一种处理办法是随机选取，这显然不是我们想要的。我们其实可以这样来处理，

Our algorithm constructs a set of vantage point candidates by random sampling,and then evaluates each of them.Evaluation is accomplished by extracting another sample,from which the median of $\prod_p(S)$,and a corresponding moment are estimated.Finally,based on these statistical images,the candidate with the largest moment is chosen.

这里的$\prod_p(S)$指的就是在该度量空间中点p和点s的距离,作者选取的statistical images是方差，我们可以从伪码中看出。

建树

和kd树一样，建树的过程是一致的，我们选出vantate point,然后递归左右建树

搜索

搜索的话，也是一样的，用结果剪枝即可

修改

这样的树不存在单旋这种方式，我们只能用替罪羊树套vantate point tree来实现

参考资料

Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces Peter N.Yianilos*

name

descirption

input

output

sample input

sample output

toturial

code

Treap

树堆Treap来源于Tree+Heap的组合, 其实就是一棵树，他的节点储存了两个键，一个是我们维护的信息，另外一个是随机数，我们不妨设前者叫key，后者叫rand_key，Treap的key满足搜索树的性质，Treap的rand_key满足堆的性质。(从某种意义上而言，笛卡尔树是key=rand_key的Treap)
特点: 若key与rand_key确定后，Treap的形态唯一，
Treap在大多数情况下显然是平衡的，但我不会证明，也没找到证明，暂时先放一下。

Treap insert

我们向一棵Treap中按照搜索树的性质插入值以后，不会破坏搜索树的特点，但是大概率导致Heap的性质被违反。考虑到单旋不会导致搜索树的性质被破坏，我们通过单旋来从新让Treap满足Heap的性质。考虑回溯，假设我们对某个子树插入了一个值，若最终插入到左子树，则可能导致左子树树根的rand_key比当前节点的rand_key大，同时因为我们只插入了一个节点，所以最多也只有一个节点的rand_key比当前节点的rand_key大，这时候如果使用zig，则树恢复平衡。

Treap erase

还是使用平衡树的操作来对Treap进行删除。如果过程中用到了前驱后继替换的技巧，这将导致替换节点的rand_key和他所处在为位置不匹配，我们就只考虑这颗子树，因为只有这颗子树的树根出现了问题，我们尝试递归向下，将位置不匹配这个现象下移，因为不匹配，必然是这个节点的rand_key比儿子们小，这时候如果左儿子的rand_key大就zig，否则zag,最后能发现这问题在向叶子结点转移，我们能够递归向下，直到最后转移到叶子上，树就恢复平衡了。

Treap 代码

无旋Treap

无旋treap，指的是不使用zig和zag来重新恢复平衡的Treap
我们使用merge和split

无旋Treap merge

merge的参数是两个treap，他返回treap合并后的结果,不妨设其中一个为T1，另一个为T2，这里还要求T1的最大key小于等于T2的最小key。merge其实很简单，如果你学过左偏树的话，会很容易理解。我们不妨设T1的根的rand_key比T2的小。那么很显然，最终结果的根为T2的根，这里我们就可以递归了，我们将T2的左子树与T1合并出T3，最后让T3最为T2新的左子树，我们得到的T2就是merge的结果。

无旋Treap split

split的参数是一个Treap和一个值W，他返回两颗Treap,其中一个的最大key小于W，另一个大于W(不需要考虑等于的情况)，这个过程依然很简单，我们考虑根就可以了，如果根的key大于w，则根和右子树分到一遍，然后递归左儿子，将得到的两个Treap中key大的那个作为之前分到一边的根的左儿子即可。

无旋Treap insert

先split，然后merge两次

无旋Treap erase

很多人这里使用了split两次然后merge三次，我认为这个不太好，常数过大，我们可以这样做，先search找到要删的点，然后merge其左右子树顶替自己即可。

无旋Treap代码

AA Tree

AA树真的很棒，虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的，AA树是一棵右倾红黑树23树，注意! 这里是23树，不是234树。

AA树的由来

Arne Andersson教授在论文Balanced search trees made simple中提到，红黑树有7种特殊情况（图片源于wiki）

为了改进，他提出了使用23树并强行要求3节点(2key-3son-node)向右倾斜，于是，我们只剩下两种情况(图片源于wiki)

为了更加容易编码，他提出不再使用红黑来标识节点，而是选择高度，这里的高度指的是黑高度，即黑色节点的高度，学习过左偏树(左翼堆)或斜堆的读者应该对这里不太陌生，这里的高度其实和左偏树或斜堆中的右距离是同一个东西。

AA树的特性

所有叶节点的level都是1
每个左孩子的level恰好为其父亲的level减一
每个右孩子的level等于其父亲的level或为其父亲的level减一
每个右孙子的level严格小于其祖父节点的level
每一个level大于1的节点有两个子节点

AA树的skew

skew 是一个辅助函数，他的本质是zig，即如果发现一个节点的左儿子与自己黑高相同，则将左儿子选择至根。这将保证右倾。

AA树中的split

split同样是一个辅助函数，他的本质是zag，即如果发现一个节点的右孙子与自己黑高相同，则将右儿子选择至根，并将黑高+1，这将保证不会出现4节点(3key-4son-node)

AA树中的insert

递归向下，找到插入位置，然后插入，最后调整，调整的时候，树会变高，对每一层递归而言，左儿子变高我们就先让其skew，这可能导致出现4节点，我们再split，对于右儿子变高的情况，这时候可能右儿子本身是一个3节点，当他变高，导致根成为了4节点，我们调用skew即可，全部统一一下，就是先skew后split

AA树中的erase

很多时候删除都是一件困难的事情，但是我们可以通过寻找前驱后继，可以保证删除的节点一定是叶子,对于删除叶子，可能树高下降，同样的，先删除后对每一层进行调整。我们前面说过，AA树只有两种结构。我们来分析一下树高下降产生的影响。

情况1

右儿子与自己同黑高

情况1.1

右儿子下降

这种情况是合法的，不需要调整

情况1.2

左儿子下降

我们观察到这里是一种较为复杂的情况，可以这样处理，让节点a和c同时黑下降，得到了

然后我们考虑到c节点的左右儿子,注意到c和a以前黑同高，所以c的右儿子cr，一定比c矮，当c下降以后，cl、c、cr同高

根据定义，这里最多还能拖出两个同黑高的，cl的右儿子clr，cr的右儿子crr

这时候我们对c执行skew，然后clr成了c的左儿子，我们再次对c执行skew，最终a-cl-clr-c-cr-crr同黑高，

接下来的一步是让我最吃惊的，非常漂亮，我们先对a进行split，然后对根的右儿子再次split，就结束了。对a进行split后我们得到,注意到这里根的高度提高了

对根对右儿子split,就结束了

情况2

右儿子与自己不同黑高

情况2.1

右儿子下降

让a节点高度降低

让a进行skew,最后因为b的右儿子高度，分两种情况


对于b的右儿子太高的时候，对a进行skew

然后对b进行split即可

情况2.2

左儿子下降

让a下降

这里可能发生c的右儿子与c同高，split（a）即可

AA树erase总结

至此我们的删除已经讨论完了，实际细分只有4种情况，这要比普通红黑树简单多了，

AA树缺点

多次旋转导致性能不及红黑树，旋转次数较多

AA树代码

left leaning red black tree

left leaning red black tree定义

在红黑树的基础上，左倾红黑树保证了3节点(2key-3son-node)的红色节点为向左倾斜，这导致了红黑树更加严格的定义,

left leaning red black tree实现

在红黑树代码的基础上，我们定义一个left leaning函数，用来调整右倾斜为左倾斜，这个函数需要适当的加入到红黑树代码当中，笔者调试了很久，找到了很多思维漏洞，把这些漏洞全部用数学的方式严格证明以后，调用left leaning函数即可。

left leaning red black tree优点

相比红黑树而言，笔者认为提升不大，真的，但是有人使用了很少的代码就实现了LLRBT，这也算一个吧，笔者是修改的红黑树，所以很难受，代码更长了。

left leaning red black tree code