【BZOJ3224】普通平衡树

学习一下各种平衡树

1.替罪羊树

一种不用旋转的平衡树，核心思想即在太不平衡时对部分子树进行重建。

设定一个参数\(\alpha\in[0.5,1)\)，那么我们希望保证两个平衡

\(\alpha\)高度平衡：树高\(h\le log_{\frac{1}{a}}n\)

\(\alpha\)大小平衡：对于一个结点\(p\)满足\(max(size_{l_p},size_{r_p})\le \alpha size_p\)

如果每个结点均满足\(\alpha\)大小平衡，假设最深的点为\(d\)，那么有

$$1\le n\alpha^{dep_d}$$

那么\(dep_d\le log_{\alpha}\frac{1}{n}=log_{\frac{1}{\alpha}}n\)，即满足\(\alpha\)高度平衡。

插入和普通BST类似，只需要判断插入操作是否导致了这一条链上结点的大小平衡被破坏，如果有的话将深度最浅的点所在子树暴力重建。重建最简单的方法就是对这棵子树中序遍历后分治建树。通过势能分析可以证明每一次插入的均摊复杂度为\(logn\)。

查询和普通BST并无区别。

删除操作比较巧妙。对于一次删除，我们并不马上移除这个点，而是直接这个点上打上删除标记，查询时跳过该点。重构时可以顺便删除打了删除标记的点。当被删除结点的个数超过总结点数的\((1-\alpha)\)倍时可以选择重构整棵树进行结构优化，并且显然这部分重构的复杂度不会超过\(O(nlogn)\)。

2.Splay

算是复习一下吧

Splay的核心操作Splay，将一个节点通过旋转调整至某一位置并保持BST性质。

旋转的话看这张图应该就能理解：

Splay分三种情况进行旋转：

1. 父亲即为目标结点。直接旋转一次即可。
2. 自己和父亲在各自父亲的同一侧。先旋转父亲一次，再旋转自己一次。
3. 自己和父亲在各自父亲的不同侧。连续旋转自己两次。

重复以上操作直到到达目标结点。

由于形态调整自由，所以可以通过旋转将一段区间位于一棵子树内从而进行区间操作。所以写这道题有点大材小用了（懒得写了）。

3.Treap

顾名思义，一个BST和堆的结合体。

给每个点随机一个权值，那么需要在Treap上保证关键字满足BST性质，权值满足堆性质。因为权值是随机的，所以期望树高是\(O(logn)\)的。

旋转式Treap

插入时先将该点像普通BST一样插入，然后不断向上旋转该点直到权值满足堆的性质。显然这样是可行的。

删除时，分三种情况：

1. 该点没有儿子，直接删除该点。
2. 该点有一个儿子，直接将儿子接到该点所在位置。
3. 该点有两个儿子，将权值较大的儿子向上旋转，继续删除过程。

那么显然这样做是不会破坏Treap的性质的。

其它操作与普通BST相同。

和Splay一样也支持区间操作。方法是新建一个权值无穷大的结点，那么这个点会被转到根节点，于是就将原序列分为了两半。

非旋转式Treap

不通过旋转实现BST的功能并维护Treap的性质。

两个操作：split和merge

split将一棵Treap中的前\(k\)个点和其它点分离为两棵Treap。在分离过程中分几种情况讨论：

1. 左子树大小等于\(k\)或\(k-1\)。显而易见，直接返回结果。
2. 左子树大小大于\(k\)。递归向左子树分离，将分离得到的右子树作为该点新的左子树。返回分离得到的左子树和自身。
3. 左子树大小小于\(k\)。递归向右子树分离，将分离得到的左子树作为该点新的右子树。返回自身和分离得到的右子树。

merge将两棵Treap按顺序合并为一棵。也分两种情况：

1. 左Treap权值大于右Treap。将左Treap的右子树与右Treap合并作为左Treap新的右子树。返回左Treap。
2. 右Treap权值大于左Treap。将左Treap与右Treap的左子树合并作为右Treap新的左子树。返回右Treap。

这两个操作都保证了Treap的两个性质。

非旋转式Treap的区间操作更简单一些，只要把区间split出来操作，最后merge回去即可。

并且由于不需要旋转，非旋转式Treap常被用于可持久化及与其它数据结构嵌套使用。