平衡树全家桶 1

Treap

Treap = Tree（BST）+ Heap

• 左旋
• 右旋

这两个显然，推一推就行

我们对每个节点附一个随机权值，用于维护小根堆/大根堆

每次，先修改（按照二叉搜索树的方式），然后转转转，使其符合堆

FHQ-Treap

无旋Treap

同样有BST和Heap的性质。（只要是Treap，其随机权值就给了其深度为log的保证）

我们有两种操作：

• spilt(root, val)

  按照val划分

  • 如果当前点 <= val，则 split(R, val)，并把得到的其中一棵树连为根节点的新右子树
  • 如果当前点 > val，则 split(L, val)

  由此，我们就可以把一棵树切成两棵树了。两棵树仍然符合bst和heap的性质，但一棵全部<=val，一棵全部>val

• merge(x1, x2)

  比较两点谁的heap值比较小，作为根节点（满足小根堆性质）

  • 如果x1比较小，就 merge(R[x1], x2)
  • 如果x2比较小，就merge(x1, L[x2])

当我们要操作（比如插入val时），我们只需要先split(L,val)得到两棵树，然后用，把新节点分别和左右merge一次即可

Splay

Splay仅有二叉搜索树的性质

• 左旋、右旋：一样

Splay怎么保持平衡的呢？

考虑当前准备旋转 x，其父亲是 y，祖父是 z

• Zig - Zig：x，y, z 三者同方向，那就先旋转y，再旋转x
• Zig - Zag：x, y, z 三者方向不同，那就旋转两次 x

那样子就很平衡了

WBLT

树：也是二叉搜索树，但只有叶节点存储信息（类似线段树），但有一个 $\alpha = 0.292$ 值。

如果左右子树较小子树的占比小于 $\alpha$，说明失去平衡了，要调整

有旋

首先假设 $R$ 是重儿子。

我们去递归判断 $R$ 是否需要平衡，如果不平衡递归下去。

回来后，我们对 $R$ 右旋，旋上去就行。

无旋

本质和旋转操作一样

如果失衡了，先保证重节点内部不失衡

然后比如左边过重，我们就merge(R[x1], x2)

然后merge(u,v)的过程是：

• 如果u, v不失衡，直接连一起

• 否则如果 $z$ 和 $w+y$ 平衡（即 $z$ 不过轻），我们就这样：

  

• 否则这样：（先各自合并，再一起合并）

  

替罪羊树

同样加入一个 $\alpha$ 因子（0.7 - 0.8），如果出事了，就要重构

重构过程就很暴力了：

• 遍历所有点，拍扁
• 暴力重建二叉搜索树

啥时候失衡：

• 插入点，往上找，第一个失衡点重构，随后不再向上检查
• 插入点，如果过深（相对深度），重构
• 删除点，标记一下，如果全树空节点过多，重构整棵树