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