登录/注册
小开开
1010
占位
2
占位
0
浏览量
占位
粉丝
占位
关注
[数据结构-平衡树]普通 FHQ
小开开
2021-10-10 15:29:29 2021-10-10
27
0

普通 FHQ_Treap从入门到精通(注释比代码多系列)

前提说明,作者写注释太累了,文章里的部分讲解来源于Oi-wiki,并根据代码,有部分增改。本文仅仅发布于博客园与知乎风的彷徨,其他地方出现本文,均是未经许可的盗窃。

芝士前置

知识名 内容
二叉搜索树 一颗每个节点的左儿子val都比自己小,右儿子val都比自己大的树
Treap 堆和平衡树的结合(Tree+Heap),其中的pri变量满足堆的性质(父亲的比自己大),val变量满足平衡树的性质

芝士引入

节点定义

struct FHQ_Node
{
    int sze, val, pri;
    int lc, rc;
    FHQ_Node()
    {
        sze = 1; //注意0号节点不能这样
        pri = rand();
    }
} FHQ_Tree[N];

基本操作

FHQ_Treap不同于传统Treap,FHQ_Treap是基于以下两个基本操作分裂合并,而不是旋转。所以也有叫无旋Treap

基本思路很简单

操作 含义
分裂 把一个树按一个界限分裂,通常是按val值分裂。小于val的节点放一颗树,大于val的节点放另一棵树。
合并 把两个树合并,通常情况下合并的两树有严格的大小关系(一般是A树的每个节点值,均小于B树)。

操作解释

分裂

分裂操作是基于递归实现的。

分裂过程接受两个参数:根指针

(u) ​ 、关键值

(key) ​ 。结果为将根指针指向的 treap 分裂为两个 treap,第一个 treap 所有结点的关键值小于$key

(​,第二个 treap 所有结点的关键值大于等于) key

(​。该过程首先判断) key$​ 是否大于

(u) ​的关键值,若大于,则说明

(u) ​及其左子树全部属于第一个 treap(当然也有一部分右子树属于,一部分不属于,所以需要递归进去),否则说明

(u) ​及其右子树全部属于第二个 treap(同理,也需要递归进去)。根据此判断决定应向左子树递归还是应向右子树递归,继续分裂子树。待子树分裂完成后按刚刚的判断情况连接 的左子树或右子树到递归分裂所得的子树中。

pair<int, int> split(int u, int _key)
{
    if (u == 0)
        return make_pair(0, 0); //如果我是个空节点,那我就算分割后的节点也是空的
    if (FHQ_Tree[u].val < _key) //当前节点小于临界key,右儿子比我大,说不定有比key大(或者等于)的,左儿子比我小,一定不可能大于等于key了
    {
        pair<int, int> ret = split(FHQ_Tree[u].rc, _key); //但是右儿子里可能有比我大的(甚至是大于key)
        FHQ_Tree[u].rc = ret.first;                       //没有key的那作为的的新右儿子,随我一起被切出去
        updata(u);                                        //我被切了,需要维护一下大小信息
        return make_pair(u, ret.second);                  //我属于小于key的部分,而被切除了小于key节点的右儿子当然就完全都是大于等于key了
    }
    else //当前节点大于等于临界key,右儿子比我还大,肯定是也大于key的,不用管。
    {
        pair<int, int> ret = split(FHQ_Tree[u].lc, _key); //同理左儿子也有可能小于我的(甚至是小于key)
        FHQ_Tree[u].lc = ret.second;                      //比大于等于key的作为我的新左儿子,和我一起走
        updata(u);                                        //我被切了,需要维护一下大小信息
        return make_pair(ret.first, u);                   //我清除掉了小于key的子树,这部分小于key,而和我在一起的都要比key大
    }
}

合并

合并操作也是基于递归的

合并过程接受两个参数:左 treap 的根指针

(x) 、右 treap

(y) 的根指针 。必须满足

(u) 中所有结点的关键值小于

(y) 中所有结点的关键值。因为两个 treap 已经有序,我们只需要考虑

(pri) ​来决定哪个 treap 应与另一个 treap 的儿子合并。若

(x) 的根结点的

(pri) 大于

(y) 的,那么 即为新根结点,

(y) 应与

(x) 的右子树合并;反之,则

(y) 作为新根结点,然后让

(x) 与

(y) 的左子树合并。不难发现,这样合并所得的树依然满足

(pri) 的大根堆性质。

int merge(int x, int y) //把x和y拼在一起(前提是x里所有节点都要比y所有节点小)
{
    if (!x || !y) //如果其中有一个节点是空的,那就别合并了,直接返回非空的那个就好了
        return x + y;
    if (FHQ_Tree[x].pri > FHQ_Tree[y].pri) //采用大根堆,x现在应该在y上面
    {
        //由于x都比y小,那么y只能挂在x的右儿子上
        //                      x全部小于y,这里顺序别搞错了
        FHQ_Tree[x].rc = merge(FHQ_Tree[x].rc, y); //考虑到x原本可能就有右儿子,先把x的右儿子和y拼在一起再说
        updata(x);                                 //y挂在了我身上,我肯定变大了,需要维护一些大小信息
        return x;                                  //y在我下面,我才是这棵树的老大
    }
    else //现在x应该在y下面了
    {
        //由于x都比y小,那么y只能考虑挂在y的左儿子上
        //                      x全部小于y,这里顺序别搞错了
        FHQ_Tree[y].lc = merge(x, FHQ_Tree[y].lc); //考虑到y原本可能就有左儿子,先把x和y的左儿子拼在一起再说
        updata(y);                                 //x挂在了我身上,我肯定变大了,需要维护一些大小信息
        return y;                                  //x在我下面,我才是这棵树的老大
    }
}

功能操作

插入

先在待插入的关键值处将整棵 treap 分裂,判断关键值是否已插入过之后新建一个结点,包含待插入的关键值,然后进行两次合并操作即可。

void ins(int _val) //插入一个点
{
    FHQ_Tree[++p].val = _val;               //先是创建一个这个样的节点
    pair<int, int> ret = split(root, _val); //以val为分界线,把这棵树分裂成两部分
    //现在我们尝试把这个新节点插入到树里
    int _new = merge(ret.first, p); //上文说道,split返回的第一个树的每个节点一定比val小,这个时候就可以把这个比val小的树和新的那个节点合并了
    root = merge(_new, ret.second); //由于新加入的节点的优先级我们是未知的,有可能比原来的根节点大,导致在原来根节点上面,发生换根
}

删除

将具有待删除的关键值的结点从整棵 treap 中孤立出来(进行两侧分裂操作),删除中间的一段(具有待删除关键值),再将左右两端合并即可。

void del(int _val) //删除一个
{
    pair<int, int> ret = split(root, _val);            //按val为分界线,现在含有val的树一定是ret.second了;
    pair<int, int> ret2 = split(ret.second, _val + 1); //再把ret.second里的节点再分一遍,现在ret2.first里的节点一定全是数为val的点
    //通常情况下,我们只删除一个节点
    int _new = merge(FHQ_Tree[ret2.first].lc, FHQ_Tree[ret2.first].rc); //左儿子和右边儿子合并,其实是其中一个优先级较大的,跑出来当爹,原来的父亲就会被孤立
    root = merge(merge(ret.first, _new), ret2.second);                  //同样的,我们删除的有可能就是原来的根,导致发生换根
}

获取排名

把一个树按分为小于

(val) 的,和大于等于

(val) 的,

(val) 的排名自然就是小于

(val) 的节点的数量+1了

int getrank(int _val) //获取排名
{
    pair<int, int> ret = split(root, _val); //以val为分界线,这样ret.first里的东西都要比val小
    int rank = FHQ_Tree[ret.first].sze + 1; //比val小的树节点全在里面,val的排名自然就是他们的数量+1了
    root = merge(ret.first, ret.second);    //别忘了把原来拆分的树合起来
    return rank;
}

通过排名取数字

和二叉搜索树一样,不再赘述。

int getnum(int _rank) //通过排名取出这个数来,返回节点的编号
{
    int now = root; //同平衡二叉树的方法一样,从根节点向下找
    while (now)
    {
        //now的左节点全是比now小的,所以比now小的数量加上1(now自己),如果正好是我们要求的点的排名,那么now就是我们要的点了
        if (FHQ_Tree[FHQ_Tree[now].lc].sze + 1 == _rank)
            break;
        else if (FHQ_Tree[FHQ_Tree[now].lc].sze >= _rank) //同理,如果比now小的数的数量大于等于我们的rank,那么排名为rand的数必须要更小,只能在now的左子树上
            now = FHQ_Tree[now].lc;
        else //rank的位置在now的后面,说明rank的数要比now还大,我们就要去右节点找
        {
            _rank -= FHQ_Tree[FHQ_Tree[now].lc].sze + 1; //由于我们要找到节点在now右节点上,右节点的排名是相对于now的排名,所以我们需要把now的排名减掉
            now = FHQ_Tree[now].rc;
        }
    }
    return now;
}

求前驱

用把原来的二叉树分裂开,一部分全是小于

(val) 的,另一部分全是大于等于

(val) 。而前驱就是前一个二叉树里最大的,用二叉搜索树的性质就能得到。

int pre(int _val) //求前驱,返回节点的值
{
    pair<int, int> ret = split(root, _val); //以val为分界线分裂
    int now = ret.first;                    //ret.first的数值都比val小
    while (FHQ_Tree[now].rc)                //找比val小的数里最大的,就是前驱了
        now = FHQ_Tree[now].rc;
    int ans = FHQ_Tree[now].val;
    root = merge(ret.first, ret.second); //别忘了把他俩合并了
    return ans;
}

求后继

用把原来的二叉树分裂开,一部分全是小于

(val+1) 的,另一部分全是大于等于

(val+1) 。而后继就是后一个二叉树里最小的,用二叉搜索树的性质就能得到。

int nxt(int _val) //求后继,返回节点的值
{
    pair<int, int> ret = split(root, _val + 1); //以val+1为分界线分裂,所有比val大的数全在ret.second里
    int now = ret.second;                       //在比val的数里找
    while (FHQ_Tree[now].lc)                    //找比val大的数里最小了的,就是后继了
        now = FHQ_Tree[now].lc;
    int ans = FHQ_Tree[now].val;
    root = merge(ret.first, ret.second); //别忘了把他俩合并了
    return ans;
}

调用方法

洛谷3369

int main()
{
    FHQ_Tree[0].sze = 0; //0号节点作为溢出点,不能有大小

    int n;
    cin >> n;
    while (n--)
    {
        int opt, val;
        cin >> opt >> val;
        switch (opt)
        {
        case 1:
            ins(val);
            break;
        case 2:
            del(val);
            break;
        case 3:
            cout << getrank(val) << endl;
            break;
        case 4:
            cout << FHQ_Tree[getnum(val)].val << endl;
            break;
        case 5:
            cout << pre(val) << endl;
            break;
        case 6:
            cout << nxt(val) << endl;
            break;
        }
    }
    return 0;
}

完整代码下载地址:https://files.cnblogs.com/files/blogs/694685/FHQ.7z

如果未来有时间我将会出一个支持序列的FHQTreap教程。

原文: https://www.cnblogs.com/Icys/p/FHQTreap.html

暂无评论