简单的前置知识。
BST
BST 是所有平衡树的基础，请看 Treap 和 Splay 等之前先看本文。
1）定义
一般是递归定义。
对于根节点，都有它的左子树的数都小于它，右边的数都大于它。
并且，左右子树也都是二叉查找树。
它的本质就是动态维护一个有序序列。
请注意，我们一般认为是不存在重复元素的。
如果有，在每一个节点上加一个计数器 $cnt$。
2）基本性质
首先，我们按照中序遍历后，一定是有序且递增的序列。
3）支持操作
前 6 个操作都可以使用 set 解决。
a. 插入
递归当前节点，如果就等于当前节点，那么计数器 $cnt$ 加1；如果比该节点小，则向左子树递归；如果比该节点大，则向有递归。
直到遇到一个空节点，就插入并结束。
b. 删除
由于常用的平衡树（ Treap,Splay ）都有自己的独特方法且较为简单，所以先不讲。
c. 查找最小值或最大值
直接一直向左 / 右一直寻找，直到为空，返回当前节点。
d. 查找前驱或后继
以前驱为例。
假设一定有该节点。
先找到该节点。
分为两种情况：
- 有左子树：先进入，然后找最大值。
- 没有左子树：找到最后一次向右递归的点，也是维护比当前值大的最小的点。
g. 求某个值的排名
h. 求排名是 k 的值
g.h. 将在 Treap 中讲解。