[学习笔记] Splay & Treap 平衡树 - 数据结构

Splay 树

又名伸展树，一种平衡二叉查找树，通过 \(\text{Splay}\) 操作不断把节点旋到根节点来维护整颗树的平衡。

说人话，很玄学的玩意，复杂度是单 log 级别的。为啥是单 log，科学的解释请移步 OI-WIKI。不科学的解释就是，通过不断 \(\text{Splay}\)，以至于整棵树不会变成一条链，再加上二叉搜索树的看家本领，有点类似于二分查找，于是复杂度就变成 \(\mathcal{O}(n\log n)\) 了。

说一说它的一些操作。从它最重要的操作开始。

Splay 操作

单次 splay 的本质就是，把某个节点与它父亲的关系调换一下。因为这是个二叉查找树，所以这种操作很方便：看图：

如果