BST 死了mā?

cqbzzlr · 2026-02-02 21:35:54 · 个人记录

这里为大家讲解一种全新的平衡树——前序平衡树：

1.前置知识

• fhq-treap 键值随机化思想；
• 朴素 BST。

2.定义

• 元素 x 的祖先均大于 x；
• 元素 x 的左子树均小于 ⌊\frac{x}{2}⌋；
• 元素 x 的右子树均大于等于 ⌊\frac{x}{2}⌋；

3.插入权值 k

在原树上暴力找到两个点 x 和 fx，将 fx 的左或右儿子从 x 改为 k，将 x 的父亲变为 k，再把 k 的儿子和父亲改一下。

有点像链表的思路：

void insert(int x,int k,int lr)://lr存储x是左儿子还是右儿子
    if x.val <= k <= father(x).val: //插入
        father(k) = father(x),father(x) = k,father(x).son[lr] = k
        if(x.val * 2 <= k) k.son[0] = x;
        else k.son[1] = x;
        //将<k/2的存在左，否则存右
    if(k * 2 <= x.val) insert(ls(x),k,0);
    else insert(rs(x),k,1);

4.删除权值 k

同样在原树上暴力找到点 x=k，然后删掉即可。

• 主播主播，那删掉之后 x 有两个儿子怎么办？
• 我们定义一个 merge 操作：

  void merge(int l,int r):
  if(siz(r)==0)ls(r)=l;
  merge(l,ls(r));

  由于我们这棵树的性质，所以一定可以把左子树一直递归放到右子树。

求排名，求第 k 大，求前驱后继都比较简单，但是我们会发现一个严重的问题：这玩意在严格递减的时候仍然会变成一条链！

性质一：离散化后的树和非离散化的树结构不同。 因为离散化后原本大于 x 的一半就可能变成小于 x 的一半，利用这点我们可以将树上的节点赋一个随机键值，保证离散化后和原数组离散化后的一致即可。

此时我们的树就变成了一棵趋近平衡的树，理论复杂度 \log n。

代码先咕着。