1. 二叉搜索树

1.1 简介

二叉搜索树是一种二叉树的树形数据结构，能将数据存储在一个树形结构上。

其满足的性质：

1. 二叉搜索树为一棵二叉树，每个节点至多有 \(2\) 个子节点；
2. 二叉搜索树中任意一个节点的左儿子值小于本节点值，右儿子值大于本节点值（左右取等亦可）；
3. 二叉搜索树的左右子树均为二叉搜索树。

以上的引申结论有：

1. 若二叉搜索树的左子树不为空，则其左子树上所有点的值均小于其根节点的值；
2. 若二叉搜索树的右子树不为空，则其右子树上所有点的值均大于其根节点的值。

基本的二叉搜索树可以完成插入，删除，按值查排名，按排名查值，前驱、后继等等。

1.2 理论

想象如何在二叉搜索树上插入一个数。

考虑在搜索树上二分，每次比较当前插入值与经过节点的值来判断插入的位置。删除亦是如此。

而按值查排名，按排名查值等可以通过维护每个节点子树大小 \(siz\) 来求解。

1. 按值查排名：类似于插入操作来找到值的位置，若走右儿子，将排名加上左儿子的子树大小加一。

2. 按排名查值：若左儿子的子树大小大于等于当前排名，则值在左子树；#若右儿子的子树大小小于当前排名，则值在右子树，排名更新为当前排名-左子树-1；

前驱为小于当前值的最大值，后继为大于当前值的最小值。

所以前驱为当前值的排名+1的值，后继为当前值+1的排名的值。

1.3 实现

1.3.1 插入

void add(int x, int v) {
  tree[x].siz++;
  if(tree[x].val == v) {
    tree[x].cnt++;
    return ;
  }
  if(v < tree[x].val) {//左子树
    if(tree[x].ls) {//有左子树
      add(tree[x].ls, v);
    } else {//无左子树
      tree[++num].val = v;
      tree[num].cnt = tree[num].siz = 1;
      tree[x].ls = num;
    }
  }
  else {//右子树
    if(tree[x].rs) {
      add(tree[x].rs, v);
    } else {
      tree[++num].val = v;
      tree[num].cnt = tree[num].siz = 1;
      tree[x].rs = num;
    }
  }
}

删除类似于插入，不过多赘述。

1.3.2 按值查排名

int lrank(int x, int v) {
  if(x == 0) return 0;
  if(v == tree[x].val) {
    return tree[tree[x].ls].siz;
  }
  if(v < tree[x].val) {
    return lrank(tree[x].ls, v);
  }
  return lrank(tree[x].rs, v) + tree[tree[x].ls].siz + tree[x].cnt;
}

1.3.3 按排名查值

int kth(int x, int rk) {
  if(x == 0) return INF;
  if(rk <= tree[tree[x].ls].siz) {
    return kth(tree[x].ls, rk);
  }
  if(rk <= tree[tree[x].ls].siz + tree[x].cnt) {
    return tree[x].val;
  }
  return kth(tree[x].rs, rk - tree[tree[x].ls].siz - tree[x].cnt);
}

1.3.4 前驱

int pre(int x, int v, int ans) {
  if(v <= tree[x].val) {
    if(tree[x].ls) {
      return pre(tree[x].ls, v, ans);
    } else return ans;
  } else {
    if(!tree[x].rs) {
      return (tree[x].val < v) ? tree[x].val : ans;
    }
    if(tree[x].cnt) {
      return pre(tree[x].rs, v, tree[x].val);
    } else return pre(tree[x].rs, v, ans);
  }
}

1.3.5 后继

int nxt(int x, int v, int ans) {
  if(v >= tree[x].val) {
    if(tree[x].rs) {
      return nxt(tree[x].rs, v, ans);
    } else return ans;
  } else {
    if(!tree[x].ls) {
      return (tree[x].val > v) ? tree[x].val : ans;
    }
    if(tree[x].cnt) {
      return nxt(tree[x].ls, v, tree[x].val);
    } else return nxt(tree[x].ls, v, ans);
  }
}

以上为远古代码，码风奇丑轻喷

不难发现，如果数据为顺序插入一条链，那么搜索树也是一条链，这样单次操作的复杂度会升到 \(O(n)\) 级别。所以，平衡树诞生了！平衡树便是用来控制树高在 \(\log n\) 级别左右并且本身为一棵二叉搜索树的数据结构。

2. fhp-treap

2.1 简介

由范浩强巨佬发明的一棵无旋 treap。

2.1.1 何为 treap

考虑如何将一棵普通二叉搜索树维护平衡。

很显然，如果每次数据的插入数据随机，那么时间复杂度就能获得均摊的机会。比如按顺序插入 1 2 3 4 5，同样的数据按 3 1 5 2 4 随机插入，树高就变底了，时间复杂度更为优秀。

但是我们无法做到将数据离线下来打乱随机插入，因为可能在期间会涉及到其他的一系列操作，使得最后得到的平衡树和某一时间戳内的不一致。