Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 后缀树 一颗后缀树是针对一个字符串而言的，该后缀树能识别这个字符串的所有后缀，能且仅能识别这个字符串的所有字串， 后缀树空间压缩 常常我们会在后缀树的边上储存字符串，而不是字符，这样可以避免大量的内存开销，每一条边，我们都记录了两个数据，字符串的起点和终点，这样就实现了后缀树的空间压缩 后缀树的构造 后缀树有很多构造算法，这里直讲最简单的，考虑一个字符串的后缀自动机，其上的paerent树便是反串的后缀树。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 字典树 字典树是我接触自动机的开端，我们先讲自动机， 自动机 自动机有五个要素，开始状态，转移函数，字符集，状态集，结束状态。 自动机识别字符串 假设我们有一个自动机，他长这个样子,他能识别字符串abc. 稍等片刻！下图正在转码中 1234graph LRstart((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。 然后我们来考虑一个复杂一点的自动 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # cartesian tree 笛卡尔树是一颗二叉树，他满足中序遍历为维护的序列，且满足堆的性质 build我们使用单调栈来维护树根到叶子的链，在单调栈的构建中完成树的构建 ct代码

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial vantate point treevp tree 是一颗二叉树，他和kd tree有着一定的相似度, 树上信息每一颗子树都要维护一个点集，对于每个节点，我们都维护一个距离d，然后将到该节点的距离小于d的点放到左儿子，其他的放到右儿子中。 vantate pointvantate 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 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # scapegoat Tree 替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是一个0.5到1的数字，当违反了这个性质，就暴力重构，将树构造为完全平衡树。 ## 替罪羊树erase 为节点打上标记scapegoat，代表这个节点已经被删除了，回溯子树大小信息。 ## 替罪羊树insert 使用bst插入的方式来插入，注意特判掉那些被打删除标记的点，就可以了 ## 替罪羊树重构 当我们erase或者insert以后，受影响的节点应该恰好构成了一条从根到目标的链，我们使用maintain来重新调整子树大小的时候，注意标记那些非法(不平衡)的节点，然后当我们maintain到根的时候，我们重构离根最近的不平衡的子树。 ## 替罪羊树代码 替罪羊树代码

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial namedescirption inputoutputsample inputsample outputtoturialcode

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 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的性质。考虑回溯，假设我们对某个子树插入了一个值，若最终插入到左子树，则可能导致左子树树根的ran ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # splay tree 伸展树，以其操作splay出名。 伸展树的本质就是bst， ## splay操作 伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## splay insert 伸展树insert的时候，先按照bst的操作insert，然后将insert的点进行splay操作即可 ## splay search 伸展树search的时候，先按照bst的操作search,对找到的节点进行splay即可 ## splay erase 伸展树erase的时候，先search,这样我们要删除的节点就成为了根，然后按照bst的操作删除即可 ## splay操作详解 ### 重新定义旋转rotate rotate(x)即交换x和x的父亲的位置，即如果x是父亲y的左儿子，则rotate(x)等价与zig(y)，反之则等价于zag(y) ### 定义spla ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 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或 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial left leaning red black treeleft 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 ...