二叉平衡树（BST）
BST 是一种数据结构，用于快速查找数据。
二叉平衡树有一个非常明显的特性：对于每一个节点 \(u\)，在其左边的数都比它小，在其右边待数都比它大。
每个点都有一个权值 cnt，用于存储这个数出现了几次。
在二叉平衡树上的每一个操作的时间与其树高成正比，约为 \(O(\log n)\)。
BST的基本操作
插入
根据二叉平衡树的性质，新加入的数分为以下几种情况：
- 比当前节点小，则将他下放到左儿子。
- 等于这个节点，则将这个节点的 \(cnt+1\)。
- 否则则下放到右儿子。
最后如果没有节点就新建一个节点，并且根据大小关系归在父亲节点的左或右儿子，将节点的 \(cnt\) 设为 \(1\)。
删除
和插入是相反操作，规则同插入操作，但当等于当前结点值的时候，要分两种情况：
- 当前结点的 \(cnt\) 值\(>1\)，即当前节点存在不止一个数，直接将 \(cnt-1\) 即可。
- 当前结点 \(cnt\) 为 \(1\)，即只有一个这样的节点，这时候如果这个点是叶子节点（下面没有儿子，直接将这个点的 \(cnt\) 设成 \(0\)，编号直接删除。如果这个节点下面还有儿子，就把下面两个元素中的任意一个元素所有变量赋值到这个位置，并且递归删除下面的点，操作同上。
查找排名为 \(x\) 的元素
根节点的排名取决于左子树的大小。
- 当左子树大小大于等于 \(x\)，则这个元素位于左子树
- 当左子树大小位于 \([x-cnt, x-1]\) 之间，则这个元素位于根节点
- 否则，这个元素位于右子树
查找元素 \(x\) 的排名
相当于搜索 \(x\)，在遍历右子树时需要加上左子树以及根节点的大小。
BST 的时间复杂度约为 \(O(\log n)\)，但是由于其特殊的性质，最坏情况下可以退化成一条链，这时候，复杂度将会退化成 \(O(n)\)，有超时风险。这时候就需要优化，优化方法有 Treap 和 Splay 等。
标签：左子,cnt,BST,元素,笔记,二叉,节点 From： https://www.cnblogs.com/ylc666/p/18295924