1. 二叉搜索树

1.1. 简介

二叉搜索树是一种二叉树,满足以下条件：

• 二叉搜索树的左子树上的所有点权值都小于根节点的权值；

• 二叉搜索树的右子树上的所有点权值都大于根节点的权值；

• 二叉搜索树的左右子树都是二叉搜索树。

但是单纯的二叉搜索树基本操作最坏的时间复杂度为 $O(n)$，因此还要通过一些方法来平衡二叉搜索树，实际时间复杂度正确。

1.2. 操作

• 遍历二叉树

  容易发现二叉搜索树的中序遍历形成的权值序列是非降序列。

• 插入一个元素

  我们在以 $root$ 为根节点的二叉搜索树中插入权值为 $val$ 的新结点。

  若 $root$ 为空，新建节点；

  若 $root$ 的权值等于 $val$，$root$ 的出现次数 $+1$；

  若 $root$ 的权值大于 $val$，在 $root$ 的左子树中插入权值为 $val$ 的节点；

  若 $root$ 的权值小于 $val$，在 $root$ 的右子树中插入权值为 $val$ 的节点。

• 删去一个元素

• 询问一个元素的排名

• 询问排名为 $k$ 的元素

• 询问一个元素的前驱

• 询问一个元素的后驱

2. Treap

2.1. 简介

treap 是一种弱平衡的二叉搜索树。顾名思义，treap 是由 tree 和 heap 组成的，那么也就说明它是通过堆来保持二叉搜索树的平衡的。具体来说，就是给每个节点随机一个值，同时 treap 满足其父亲的随机值一定要大于其两个儿子的，在操作时维护即可。