【学习笔记】SBT学习笔记

如果不知道BST的读者可以看下面这篇


本文SBT采用数组方式存储

建议不要用使用SBT,(过于鸡肋)

一、什么是SBT

SBT , 即 Size Balanced Tree,是一种平衡二叉排序树,根据其节点中 Size 域大小进行平衡,由陈启峰于2006年在冬令营提出

二、为什么写SBT:

  1. 书写简单:在常用的平衡树( Spaly , Treap , AVL , Red-Black Tree ……)中,SBT的码量较小,只是在原有 BST 的基础上加入 Maintain 函数以及对Size域的一些调整.
  2. 理解简单:SBT 的基本思想相对于别的平衡树( Splay , AVL ,RBT……)来说更加容易被初学者所接受
  3. 效率较高:其核心算法 Maintain 的复杂度平摊为O(1)(不会证),(证明过程可见论文),且其趋近于一棵完美的二叉排序树。

三、平衡性质

SBT总满足:

$$1.Size[Right[t]] >= Size[Left[Left[t]]],Size[Right[Left[t]]]$$

$$2.Size[Left[t]] >= Size[Left[Right[t]]],Size[Right[Right[t]]]$$

翻译过来即:
一个节点的左右儿子的子树大小总不小于其兄弟的儿子(侄子)的子树大小

而这种平衡性质便是以 Maintain 来维持

四、基本操作

0、声明:

int n, root, tot;
int Right[100100], Left[100100], Size[100100], Val[100100];

1、旋转

实现 Maintain 的基本操作即 左旋 与 右旋

左右旋.PNG

左旋即将操作点(L)变为其先前右儿子(P)的左儿子,先前右儿子(P)变为操作点(L)的父亲,同时保持BST性质。(如图,先前P为L的右儿子,现在L为P的左儿子)

void Left_rotate(int &p)//
{
    int k = Right[p];
    Right[p] = Left[k];//将p的右儿子变为其原本右儿子的左儿子
    Left[k] = p;//将p原本的右儿子的左儿子变为p
    Size[k] = Size[p];//k取代p的Size值
    Size[p] = Size[Right[p]] + Size[Left[p]] + 1;//计算p的大小值
    p = k;
}

右旋即将操作点(P)变为其先前左儿子(L)的右儿子,先前左儿子(L)变为操作点(P)的父亲,同时保持BST性质。(如图,先前L为P的左儿子,现在P为L的右儿子)

void Right_rotate(int &p)//右旋与左旋相反
{
    int k = Left[p];
    Left[p] = Right[k];
    Right[k] = p;
    Size[k] = Size[p];
    Size[p] = Size[Right[p]] + Size[Left[p]] + 1;
    p = k;
}

2、Maintain

在什么情况下会使用 Maintain 呢?就是在性质1或2不满足,平衡树不平衡。所以,当一棵 SBT 变化的时候会使用 Maintain。
在所有的基本操作中,改变 BST 的也就两个,Insert 和 Delete。而 Delete 是不改变树的形态的。

虽然它(Delete)会破坏SBT的结构,但因为使用 Insert 操作,它还是一棵高度为O(log2 K)的 SBT 。这里的 K 是所有插入节点的个数,而不是当前节点的个数

而插入一个节点后中,我们需要对插入过程中经过的点进行 Maintain 操作,否则以这些点为根的子树有可能不平衡。
Maintain(p)指的是调整以 p 为根的 SBT 。

我们可以发现,性质1,2是基本对称的,所以我们可以先讨论性质1,再类比性质2
性质1.a: 如图,Size[Right[t]] < Size[Left[Left[t]]],
1.PNG
(1)为了配平,我们可以先将L进行右旋操作,变为下图;
2.PNG
(2)如图,有可能Size[C] or Size[D] 大于 Size[B] ,所以需要再次 Maintain(right[p])(p在上一次操作中指向了L);

(3)调整完后,我们会发现以L为根节点的子树仍有可能不平,所以需要继续执行Maintain(p);

性质1.b: 如图,Size[Right[t]] < Size[Right[Left[t]]],
3.PNG
(1)先调整以L为根节点的子树,对L执行左旋操作,变为下图
4.PNG
(2)再对P执行右旋操作,变为下图。
5.PNG
(3)我们可以发现,虽然这棵树炒鸡不平衡,但子树 A,E,F,R只是挪了挪位置,其平衡性质并没有改变,所以我们只需要再Maintain(L),Maintain(P),Maintain(B)即可。

性质2.a:Size[Left[t]] < Size[Right[Right[t]]]:
与性质1.a刚好相反,可以自行画图理解。

性质2.b:Size[Left[t]] < Size[Left[Right[t]]]:
与性质1.b刚好相反,可以自行画图理解。
其实是我不想画图了

综上,我们可以大致的写出如下程序:

void Maintian(int &p)
{
    if (Size[Left[Left[p]]] > Size[Right[p]])
    {
        Right_rotate(p);
        Maintian(Right[p]);
        Maintian(p);
        return;
    }
    if (Size[Right[Left[p]]] > Size[Right[p]])
    {
        Left_rotate(Left[p]);
        Right_rotate(p);
        Maintian(Left[p]);
        Maintian(Right[p]);
        Maintian(p);
        return;
    }
    if (Size[Left[Left[p]]] > Size[Right[p]])
    {
        Left_rotate(p);
        Maintian(Left[p]);
        Maintian(p);
        return;
    }
    if (Size[Right[Left[p]]] > Size[Right[p]])
    {
        Right_rotate(Right[p]);
        Left_rotate(p);
        Maintian(Left[p]);
        Maintian(Right[p]);
        Maintian(p);
        return;
    }
    return;
}

不过我们还可以有另一种写法,即用一个bool参数flag来表示其究竟是违反了性质1还是性质2,并且将一些重合的操作写在外面

void Maintian(int &p, bool flag)
{
    if (!flag)
    {
        if (Size[Left[Left[p]]] > Size[Right[p]])
            Right_rotate(p);
        else if (Size[Right[Left[p]]] > Size[Right[p]])
        {
            Left_rotate(Left[p]);
            Right_rotate(p);
        }
        else
            return;
    }
    else
    {
        if (Size[Right[Right[p]]] > Size[Left[p]])
            Left_rotate(p);
        else if (Size[Left[Right[p]]] > Size[Left[p]])
        {
            Right_rotate(Right[p]);
            Left_rotate(p);
        }
        else
            return;
    }
    Maintian(Left[p], false);//以Left[p]为根的子树中,左子树定比右子树的儿子子树的大小要大
    Maintian(Right[p], true);//以Right[p]为根的子树中,右子树定比左子树的儿子子树的大小要大
    Maintian(p, true);
    Maintian(p, false);
}

至于 Maintain 的效率云云,可见陈启峰大佬的论文:中文译文版 英文版

3、Insert

与 BST 差不多,只是多加了 Maintain 与 对Size的处理,故直接放代码:

void Insert(int &p, int &v)
{
    if (!p)
    {
        p = ++tot;
        Val[++p] = v;
        Size[p] = 1;//Size
        return;
    }
    Size[p]++;//Size
    if (v < Val[p])
        Insert(Left[p], v);
    else
        Insert(Right[p], v);
    Maintian(p, v >= Val[p]);//Maintain
}

4、Delete
与 BST 差不多,只需再注意对 Size 的处理,直接放代码:

int Delete(int &p, int x)
{
    Size[p]--;
    int tmp;
    if (x == Val[p] || (x < Val[p] && !Left[p]) || (x > Val[p] && !Right[p]))
    {
        tmp = Val[p];
        if (!Left[p] || !Right[p])
            p = Left[p] + Right[p];
        else
            Val[p] = erase(Left[p], Val[p] + 1);
        return tmp;
    }
    if (x < Val[p])
        tmp = erase(Left[p], x);
    else
        tmp = erase(Right[p], x);
    return tmp;
}

5、Rank:

查找一个值在树中的大小排名,细节在代码中

int Rank(int &p, int &v)
{
    if (p == 0)
        return 1;
    if (v <= Val[p])
        return Rank(Left[p], v);
    else
        return Size[Left[p]] + 1 + Rank(Right[p], v);
}

6、Select:

查找一个排名在树中的具体值,细节在代码中:

int Select(int &p, int k)
{
    if (Size[Left[p]] + 1 == k)
        return Val[p];
    if (k <= Size[Left[p]])
        return Select(Left[p], k);
    else
        return Select(Right[p], k - 1 - Size[Left[p]]);
}

7、Find:

查找一个值是否存在

bool Find(int &p, int &v)
{
    if (p == 0)
        return 0;
    if (v < Val[p])
        return Find(Left[p], v);
    else if (v == Val[p])
        return 1;
    else
        return Find(Right[p], v);
}

8、找前驱/后继:

细节在代码中:

int GetLast(int &p, int &v)//前驱
{
    if (p == 0)
        return v;
    int x;
    if (v <= Val[p])
        return GetLast(Left[p], v);
    else
    {
        x = GetLast(Right[p], v);
        if (x == v)
            x = Val[p];
        return x;
    }
}
int GetNext(int &p, int &v)//后继
{
    if (p == 0)
        return v;
    int x;
    if (v >= Val[p])
        return GetNext(Right[p], v);
    else
    {
        x = GetNext(Left[p], v);
        if (x == v)
            x = Val[p];
        return x;
    }
}

9、完整代码:

#include <bits/stdc++.h>
using namespace std;
int n, root, tot;
int Right[100100], Left[100100], Size[100100], Val[100100];
void Right_rotate(int &p)
{
    int k = Left[p];
    Left[p] = Right[k];
    Right[k] = p;
    Size[k] = Size[p];
    Size[p] = Size[Right[p]] + Size[Left[p]] + 1;
    p = k;
}
void Left_rotate(int &p)
{
    int k = Right[p];
    Right[p] = Left[k];
    Left[k] = p;
    Size[k] = Size[p];
    Size[p] = Size[Right[p]] + Size[Left[p]] + 1;
    p = k;
}
void Maintian(int &p, bool flag)
{
    if (!flag)
    {
        if (Size[Left[Left[p]]] > Size[Right[p]])
            Right_rotate(p);
        else if (Size[Right[Left[p]]] > Size[Right[p]])
        {
            Left_rotate(Left[p]);
            Right_rotate(p);
        }
        else
            return;
    }
    else
    {
        if (Size[Right[Right[p]]] > Size[Left[p]])
            Left_rotate(p);
        else if (Size[Left[Right[p]]] > Size[Left[p]])
        {
            Right_rotate(Right[p]);
            Left_rotate(p);
        }
        else
            return;
    }
    Maintian(Left[p], false);
    Maintian(Right[p], true);
    Maintian(p, true);
    Maintian(p, false);
}
void Insert(int &p, int &v)
{
    if (!p)
    {
        p = ++tot;
        Val[++p] = v;
        Size[p] = 1;
        return;
    }
    Size[p]++;
    if (v < Val[p])
        Insert(Left[p], v);
    else
        Insert(Right[p], v);
    Maintian(p, v >= Val[p]);
}
int Delete(int &p, int x)
{
    Size[p]--;
    int tmp;
    if (x == Val[p] || (x < Val[p] && !Left[p]) || (x > Val[p] && !Right[p]))
    {
        tmp = Val[p];
        if (!Left[p] || !Right[p])
            p = Left[p] + Right[p];
        else
            Val[p] = erase(Left[p], Val[p] + 1);
        return tmp;
    }
    if (x < Val[p])
        tmp = erase(Left[p], x);
    else
        tmp = erase(Right[p], x);
    return tmp;
}
int Rank(int &p, int &v)
{
    if (p == 0)
        return 1;
    if (v <= Val[p])
        return Rank(Left[p], v);
    else
        return Size[Left[p]] + 1 + Rank(Right[p], v);
}
int Select(int &p, int k)
{
    if (Size[Left[p]] + 1 == k)
        return Val[p];
    if (k <= Size[Left[p]])
        return Select(Left[p], k);
    else
        return Select(Right[p], k - 1 - Size[Left[p]]);
}
int GetLast(int &p, int &v)
{
    if (p == 0)
        return v;
    int x;
    if (v <= Val[p])
        return GetLast(Left[p], v);
    else
    {
        x = GetLast(Right[p], v);
        if (x == v)
            x = Val[p];
        return x;
    }
}
int GetNext(int &p, int &v)
{
    if (p == 0)
        return v;
    int x;
    if (v >= Val[p])
        return GetNext(Right[p], v);
    else
    {
        x = GetNext(Left[p], v);
        if (x == v)
            x = Val[p];
        return x;
    }
}
void LDR(int &p)
{
    if (p == 0)
        return;
    LDR(Left[p]);
    printf("%d ", Val[p]);
    LDR(Right[p]);
    return;
}
bool Find(int &p, int &v)
{
    if (p == 0)
        return 0;
    if (v < Val[p])
        return Find(Left[p], v);
    else if (v == Val[p])
        return 1;
    else
        return Find(Right[p], v);
}
int Max(int &p)
{
    if (Right[p] != 0)
        return Max(Right[p]);
    else
        return Val[p];
}
int Min(int &p)
{
    if (Left[p] != 0)
        return Min(Left[p]);
    else
        return Val[p];
}

int main()
{
    scanf("%d", &n);
    int k, v;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &k, &v);
        if (k == 1)
            Insert(root, v);
        else if (k == 2)
            Delete(root, v);
        else if (k == 3)
            printf("%d\n", Rank(root, v));
        else if (k == 4)
            printf("%d\n", Select(root, v));
        else if (k == 5)
            printf("%d\n", GetLast(root, v));
        else if (k == 6)
            printf("%d\n", GetNext(root, v));
        else if (k == 7)
            LDR(root);
    }
    return 0;
}

四、推荐习题:

1 【模板】普通平衡树
2、郁闷的出纳员

五、关于 SBT 的几个疑惑暂时只有一个

1、为啥没多少人用SBT???

六、参考文献:

1、感谢陈启峰大佬的论文(虽然我并没有找到原版)
2、感谢 I_AM_HelloWordolinr 的博客

Last modification:August 25th, 2019 at 05:01 pm

2 comments

  1. Sun

    为什么不试试Splay呢,Splay多好啊。还有FHQ_Treap也很不错啊,可以可持久化。替罪羊树没什么用,实际运用范围不是很广,并且这种"权值平衡"的方法优化KDT是最好不过了。

    何况替罪羊树上不了树的,不康康Splay的话LCT都学不会。

    1. fpjo
      @Sun

      感谢大佬的建议哈,不过我第一个学的平衡树是SBT哈^_^
      实在是我太弱,现在还只会SBT,以后会肝别的别的树,计划写一个平衡树系列的学习笔记

Leave a Comment