nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 后缀树 一颗后缀树是针对一个字符串而言的，该后缀树能识别这个字符串的所有后缀，能且仅能识别这个字符串的所有字串， 后缀树空间压缩 常常我们会在后缀树的边上储存字符串，而不是字符，这样可以避免大量的内存开销，每一条边，我们都记录了两个数据，字符串的起点和终点，这样就实现了后缀树的空间压缩 后缀树的构造...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 字典树 字典树是我接触自动机的开端，我们先讲自动机， 自动机 自动机有五个要素，开始状态，转移函数，字符集，状态集，结束状态。 自动机识别字符串 假设我们有一个自动机，他长这个样子,他能识别字符串abc. 稍等片刻！下图正在转码中 1234graph LRstart((start))--a-->...

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

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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # scapegoat Tree 替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是一个0.5到1的数字，当违反了这个性质，就暴力重构，将树构造为完全平衡树。 ## 替罪羊树erase 为节点打上标记scapegoat，代表这个节点已经被删除了，回溯子树大小信息。 ##...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial namedescirption inputoutputsample inputsample outputtoturialcode

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Treap 树堆Treap来源于Tree+Heap的组合, 其实就是一棵树，他的节点储存了两个键，一个是我们维护的信息，另外一个是随机数，我们不妨设前者叫key，后者叫rand_key，Treap的key满足搜索树的性质，Treap的rand_key满足堆的性质。(从某种意义上而言，笛卡尔树是key=rand_key的Treap) 特点:...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # splay tree 伸展树，以其操作splay出名。 伸展树的本质就是bst， ## splay操作 伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## splay insert 伸展树insert的时候，先按照bst的操作insert，然后将insert的点进行splay操作即可 ## splay...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial AA Tree AA树真的很棒，虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的，AA树是一棵右倾红黑树23树，注意! 这里是23树，不是234树。 AA树的由来 Arne Andersson教授在论文Balanced search trees made simple中提到，红黑树有7种特殊情况（图片源于wiki）...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial left leaning red black treeleft leaning red black tree定义 在红黑树的基础上，左倾红黑树保证了3节点(2key-3son-node)的红色节点为向左倾斜，这导致了红黑树更加严格的定义, left leaning red black tree实现 在红黑树代码的基础上，我们定义一个left...