<--------------【Loading…】

正在更新中！

前言

学了这么久发现自己还不会写平衡树相关的板子，所以来再顺一遍思路。

$$\Huge【平衡树】目录$$

零、前置知识——BST

PS：前置知识篇幅较长，若已经学会可以跳过。

定义

先定义一种数据结构，叫做二叉搜索树。

这是一棵二叉树，每个节点有一个权值，这棵二叉搜索树的特殊之处就在于：

1. 它左子树的所有点权值都小于它。
2. 它右子树的所有点权值都大于它。

根据定义，我们发现它的性质：中序遍历是一个单调递增的序列。

在二叉搜索树上基本操作花费的时间与树高成正比。
对于有 $n$ 个节点的二叉搜索树，操作的最优复杂度为 $O(n \log n)$，最劣为 $O(n)$，随机生成的期望树高为 $O(\log n)$。

基本操作

遍历二叉树

显然 dfs 即可，依照性质采用中序遍历可以获得单调递增序列。

查找最小最大值

从根节点开始，一路向左可以到达最小，一路向右可以到达最大。

查找某个数 x 是否存在

从根节点开始。

• 若当前节点权值等于 x，则一定存在。
• 若当前节点权值小于 x，则往右子树。
• 若当前节点权值大于 x，则往左子树。

插入元素 x

这里我们定义，如果一个数出现多次，则在相应的节点上记录一个 cnt，标记它出现的次数。

• 若当前节点为空，则在此新建一个节点，权值设为 x，cnt 设为 $1$。
• 若当前节点权值等于 x，则当前点 cnt 加 $1$。
• 若当前节点权值小于 x，则往右子树。
• 若当前节点权值大于 x，则往左子树。

删除元素 x

前面就不说了，总之你得先找到这个节点。

• 若 cnt 大于 $1$，则 cnt 减 $1$。
• 若 cnt 等于 $1$，则：
  • 若它没有左右儿子，直接删除。
  • 若它只有一个儿子，则用这个儿子代替它。
  • 否则用左子树最大或右子树最小代替它。
    • 即把这两个节点中的一个数据复制到 x 这个位置。
    • 并递归下去删除那个点。

求元素 x 排名

相当于搜索 x，每次向右递归的时候排名加上它左子树大小和当前节点本身出现次数。

查找排名为 k 的元素

由于中序遍历的性质，根节点的排名取决于左子树大小。

• 如果左子树大小大于等于 k，则一定在左子树。
• 如果左子树大小为 [k - cnt, k - 1]，则这个元素位于根节点。
• 否则往右子树递归。

至此，我们学会了二叉搜索树（BST）这一数据结构。

由于前面提到，二叉搜索树的基本操作最劣可以达到 $O(n)$，例如依次插入 1 2 3 4 5 ...，可以通过构造数据使得它直接挂掉。
因此需要进行优化，如旋转操作或 Treap、Splay 等平衡树。