Y快速前缀树

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

Y快速前缀树

继X快速前缀树以后,Dan Willard又提出了X快速前缀树的改进版本

改进X快速前缀树

我们还是继续考虑n个小于M的整数(n<M),我们按照大小,从小到大分组,每组的元素的个数在区间$[\frac{lgM}{4},2lgM]$上,对每组构建一颗普通平衡树,这样我们一共会得到$\frac{n}{2lgM}$到$\frac{4n}{lgM}$颗树,我们在这些树中取一个随便的值r,r要在平衡树的最大和最小值之间,这样我们每棵树对应了一个r,把所有的r作为键,其对应的平衡树作为值放到X快速平衡树中,这就是Y快速平衡树。

Y快速前缀树的查找前驱后继

首先在上层X前缀树上查找前驱和后继,最终我们会定位到两个叶子节点,也就对应了两颗普通平衡树,我们在这两颗普通平衡树里面直接找前驱后继然后合并就结束了。总复杂度$lglg(\frac{n}{lgM})+2*lg(lgM)=lglgM$

Y快速前缀树的插入

先在X前缀树上查询前驱后继,然后在其对应的平衡树上插入真正要插入的值,总复杂度$lglg(\frac{n}{lgM})+lglgM=lglgM$,这里有可能导致插入的值太多,进行分裂,我们来看一下这次分裂前插入了多少元素,我们考虑最坏的情况,不妨设之前也是分裂的,那么他的大小为$lgM$,到这次分裂一共插入了lgM+1个元素,导致现在的大小超过了2lgM,于是这lgM次插入的均摊分裂复杂度为$\frac{lg(\frac{n}{lgM})}{lgM}\lt 1$,于是总复杂度为$lglgM$

Y快速前缀树的删除

同样的,我们还是先查询前驱后街,然后在对应的平衡树上删除真正要删除的值,总复杂度为$lglg(\frac{n}{lgM})+lglgM=lglgM$,这里有可能导致平衡树上剩下的值太少,我们考虑合并,合并后如果依然太大,比方说大于lgM,我们就再次分裂为两个平衡树即可。这里可以证明,均摊复杂度依然是O1,因为从$\frac{lgM}{2}$到$\frac{lgM}{4}$也要$\frac{lgM}{4}$次删除,均摊下来,依然是O1,为了懒惰删除,我们甚至可以不必要求合并后超过lgM猜分裂,到2lgM也行。懒惰总是优秀的。于是总体复杂度为$lglgM$

总结

至此,Y快速前缀树的所有操作均为lglgM了.

代码

欠着欠着,以后再补。