「OI」平衡树

替罪羊树

替罪羊树是一种简单的二叉搜索树,它通过不断地重构来维护自身的平衡性,进而防止自身退化。

基本思想

替罪羊树的思想十分简单,它在大多数时候都只是一颗普通的二叉搜索树。如果在插入结点后使得它退化成为链,那么一定会有一个结点的左右儿子极端不平衡。

替罪羊树通过这种性质,每次检查一个结点的左右子树是否平衡,一旦不平衡立即重新构这颗子树,防止退化。

存储结构

替罪羊树的基本存储结构是结点,也就是是说,我们所有的信息都被存储在结点上。

struct Node{
    int fa,ch[2];
    int siz;
    int val;
    #define fa(x) unit[(x)].fa
    #define ch(x) unit[(x)].ch
    #define siz(x) unit[(x)].siz
    #define val(x) unit[(x)].val
    #define lson(x) ch(x)[0]
    #define rson(x) ch(x)[1]
};
Node unit[MAXN];

基本操作

替罪羊树的基本操作与其他平衡树很相似,本质上就是二叉搜索树的操作。

核心操作

替罪羊树的核心操作就是拍扁重构。

首先,我们需要判定一个结点的子树要不要进行重构,我们使用一个常数来判断,如果一个结点的儿子的子树大小占它子树大小的比例超过了这个常数,我们则判定为需要重构。

一般重构判定常数取 $0.7\sim 0.8$。

实际应用

下面我们按照惯例解决一下模板题。

  • 普通平衡树
    • insert 使用二叉搜索树的插入操作即可;
    • del 使用二叉搜索树的删除操作即可;
    • rnk 使用二叉搜索树的查排名操作即可;
    • find 使用二叉搜索树的查询操作即可;
    • pre 使用二叉搜索树的前驱操作即可;
    • suf 使用二叉搜索树的后继操作即可;
  • 文艺平衡树
    • reverse 应该做不到吧。

快速解决了模板题目,替罪羊树实在是太棒了。

Pages: 1 2 3 4