【数据结构】二叉搜索树
WeLikeStudying · · 算法·理论
- 对线段树的替代性真的不强，常数基本上比线段树的大。
- 特点是中序遍历代表一个序列。
如果是区间旋转和翻转当我没说。- 所以这里重点讲树堆（
\text{Treap} ）和伸展树。 - 后期实现的代码会更加精简，有兴趣可以看看。
旋转
- 旋转是许多平衡树算法的难点所以需要仔细讲解。
- 简单来说就是在中序遍历不变的情况下改变树的结构。
- 首先介绍单旋：
- 从左往右称为右旋，从右往左称为左旋，如何简洁地写出旋转的代码呢？
- 右旋可以类比。
树堆
- 普通的二叉搜索树容易被卡。
- 对于数据离线的情况下，随机排序一遍是好的，因为可以证明期望树高是
O(\log n) 。 - 但有的时候要同时支持一些修改操作，于是我们就需要二叉搜索树保持一个动态平衡的状态。
- 树堆通过随机权值同时用旋转让权值保持堆序来实现随机平衡的效果，单次操作期望
O(\log n) 。 - 下面左边和右边分别是两种旋转的方式。
- 插入节点后要往上旋转，删除节点后要往下旋转到叶子。
- 每次维护子树的大小就可以查询第
k 大了，如何在旋转时顺便维护子树大小呢？ - 显然可以。
- 具体实现中，我们通常使用
0 号节点以保证正确的边界情况处理，它用作表示空节点和防止越界访问。 - 注意是大根堆还是小根堆，注意每次更改都要维护堆性质，注意分清
\text{son}(0,i) ，以下是比较复杂的删除节点操作的代码。 - 注意加入点后要声明加入点的父亲，要不然后面转不上去。
- 树堆带注释实现。
- 普通平衡树树堆实现。
- 普通平衡树加强版树堆实现（推荐）。
- 非递归普通平衡树树堆实现。
可分裂树堆
- 由于树的结构相对稳定，可以方便地支持可持久化。
- 而且比旋转操作要好打，据说代码量也很小。
- 核心操作就是合并和分裂
当然还有随机种子。 - 荣誉属于范浩强先生，所以此数据结构也被称为
\text{Fhq Treap} 。 - 有按值合并和按排名分裂两种。
- 容易发现合并与分裂的核心在一条有趣的链上（注意合并要求值域不交），所以复杂度
O(h) 。 - 合并：
- 分裂：
- 带注释可分裂树堆实现。
- 普通平衡树可分裂树堆实现。
- 普通平衡树加强版可分裂树堆实现（数组开太小，爆零两行泪）。
- 文艺平衡树可分裂树堆带注释实现。
- 文艺平衡树可分裂树堆实现（作者的
\text{get node} 写错了让\text{sz[0]=1} ）（注意分裂操作不同了，上传与下传也不同了，每次\text{split} 的时候记得下传懒标记）。 - 可持久化平衡树可分裂树堆代码实现（核心是在分裂的时候新建节点，合并的时候不新建节点）。
- 可持久化文艺平衡树可分裂树堆代码实现（核心是经常新建节点）。
- 维护数列可分裂树堆实现。
- 火星人可分裂树堆实现。
- 括号修复可分裂树堆实现。
伸展树
- 每次对一个节点进行操作就直接把它旋转到根节点。
- 如果乱旋转会被卡，但是用一种特殊的旋转方式就不会被卡，而且可以证明均摊的复杂度为
O(\log n) （所以不能持久化）。 - 虽然常数很大但是
\text{LCT} 需要它。 - 需要进行一个操作
\text{splay}(u,v) 表示将节点u 旋转到节点v 的儿子处，正因为如此，伸展树的每个节点都必须记录其父亲，每个伸展树的旋转操作都显得更加复杂，更何况本来就还有双旋操作。 - 一种相对于
\text{splay} 更简单的实现（你容易明白为什么）： - 单旋的实现完成了，我们不禁想问，那么应该如何进行旋转呢？
- 如果
u 的父亲就是v 节点的儿子，那么进行一步单旋，然后完成任务。 - 否则，对于
u 的父亲的父亲相对于u 的父亲，与u 的父亲相对于u 的左右情况，我们有两类旋转方式。 - 链状就是先转父亲再转儿子。
- 折线状就是先转儿子再转父亲，这就是神奇的双旋。
- 知道了双旋怎么实现我们也可以实现
\text{splay} 操作了。 - 给两张图比较一下单旋和双旋的优劣：
- 接下来就是如何实现一些细节操作的事情了，详见代码，注意细节。
- 需要提示一点：
\text{splay} 相当于对它的每一个操作都有（甚至是比较大的可能）可能达到\Theta(n) ，所以这也说明了\text{splay} 的一个原则：尽量破坏原有的树的结构，在我们访问的向下形成的访问链中，尽量处理访问到的最深的地方，尤其是访问前驱和后继的时候。 - 对了，为了方便处理我们通常会加一个超级前驱
-\infty 和超级后继+\infty ，它们的个数都是0 （免得算大小时被记入）。 - 由于
\text{splay} 的操作较为灵活，看起来很复杂但实际实现代码长度和旋转版本的树堆差不多。 - 有的时候
\text{splay} 也需要实现一些区间操作，懒标记可以在向下找的时候下传，\text{splay} 的时候\text{update} 。 - 访问前驱：
- 伸展树带注释实现。
- 普通平衡树代码伸展树实现。
- 普通平衡树加强版伸展树实现（推荐）。
- 带注释文艺平衡树伸展树实现。
- 文艺平衡树伸展树实现（作者这里将
\text{v} 的节点编号设为\text{bool} 然后调试了很久\text{qwq} ）。 - 维护数列伸展树实现。
- 火星人伸展树实现。
- 括号修复伸展树实现。
pb_ds
- 这是一种十分高级的平衡树（滑稽），它基于政策而非算法本身，其中红黑树常数较小，也最常使用。
- 与
\text{set} 最重要的不同在于内部封装了\text{order\_of\_key} 和\text{find\_by\_order} 。（还有一个似乎没什么太大用处的支持值域不交的合并） - 所以它几乎可以完全代替我们的普通集合操作，但是相对复杂的题目仍然需要我们自己实现一棵平衡树。
- 不过注意，一个操作功能越多，往往代表它的常数越大，所以请
\text{keep it simple and stupid} 。
总结
- 这些东西是给后面的做准备的，但是不得不说打得真是心累，希望有用吧。
- 任何支持增删的半群信息合并都可以用这个玩意，也就是动态数组的半群信息合并使用这个十分方便，比如这题。