非旋treap

核心思想
核心操作
其他操作
参考程序

核心思想

主要的思想与treap是一样的。通过让二叉查找树同时满足堆（随机参数）的性质来防止深度过大。与普通treap不同的是非旋treap通过树的分裂与合并来实现这一点，而非旋转。

核心操作

Update

如果是要实现类似于 set<int> 的功能，可以不用这一部分。本文以 loj104 为例，我们需要在这里更新节点的 \(Size\) 信息。

void node::Update()

{

    Size = Count;

    if (LeftChild != NULL)

        Size += LeftChild->Size;

    if (RightChild != NULL)

        Size += RightChild->Size;

    return;

}

Split

将一个非旋treap按关键字 \(x\) 分成两个，其中一个树中关键字大小不超过 \(b\) ，另一个树中关键字严格大于 \(x\)。

std::pair<node *, node *> Split(node *Rt, int x)

{

    if (Rt == NULL)

        return std::pair<node *, node *>(NULL, NULL);

    if (x < Rt->Value)

    {

        std::pair<node *, node *> Temp = Split(Rt->LeftChild, x);

        Rt->LeftChild = Temp.second;

        Rt->Update();

        return std::pair<node *, node *>(Temp.first, Rt);

    }

    else

    {

        std::pair<node *, node *> Temp = Split(Rt->RightChild, x);

        Rt->RightChild = Temp.first;

        Rt->Update();

        return std::pair<node *, node *>(Rt, Temp.second);

    }

}

Merge

合并两棵非旋treap，其中一棵中关键字严格小于另外一棵，使得新的非旋treap同时满足二叉查找树和堆的性质。

可以递归实现，每次合并使随机的 priority 小的（或大的）在上即可。

node *Merge(node *l, node *r)

{

    if (l == NULL)

        return r;

    if (r == NULL)

        return l;

    if (l->Priority <= r->Priority)

    {

        l->RightChild = Merge(l->RightChild, r);

        l->Update();

        return l;

    }

    else

    {

        r->LeftChild = Merge(l, r->LeftChild);

        r->Update();

        return r;

    }

}

其他操作

Insert & Delete

首先查询是否需要改变节点的数量。如果不需要，直接修改 Size 即可。否则：

Insert: 将树分成小于 \(x\) 和大于 \(x\) 两部分，然后合并这两棵树和新节点 \(x\) 。

Delete：将树分成小于 \(x\) 、等于 \(x\) 和大于 \(x\) 三个部分，然后删除等于 \(x\) 的部分并且合并小于 \(x\) 的部分和大于 \(s\) 的部分。

void Insert(int x)

{

    node *T = Find(x);

    if (T != NULL)

    {

        Update(x, 1);

        return;

    }

    std::pair<node *, node *> Temp = Split(Root, x);

    Temp.first = Merge(Temp.first, new node(x));

    Root = Merge(Temp.first, Temp.second);

    return;

}

int Delete(int x)

{

    node *T = Find(x);

    if (T == NULL)

        return 1;

    if (T->Count > 1)

    {

        Update(x, -1);

        return 0;

    }

    std::pair<node *, node *> Temp1 = Split(Root, x - 1);

    std::pair<node *, node *> Temp2 = Split(Temp1.second, x);

    delete Temp2.first;

    Root = Merge(Temp1.first, Temp2.second);

    return 0;

}

Rank & Query & Precursor & Successor

这些就和一般的二叉查找树差不多，就不赘述了。

参考程序

loj 104

#include <cstdio>

#include <algorithm>

const int INF = 1e7 + 10;

struct node

{

    int Value, Priority, Size, Count;

    node *LeftChild, *RightChild;

    node()

    {

        Value = Priority = Size = Count = 0;

        LeftChild = RightChild = NULL;

        return;

    }

    node(int _Value)

    {

        Value = _Value;

        Priority = rand();

        Size = Count = 1;

        LeftChild = RightChild = NULL;

        return;

    }

    inline void Update();

};

struct noneRotateTreap

{

    node *Root;

    noneRotateTreap()

    {

        Root = NULL;

        return;

    }

    inline std::pair<node *, node *> Split(node *Rt, int x);

    inline node *Merge(node *x, node *y);

    inline node *Find(int x);

    inline void Update(int x, int State);

    inline void Insert(int x);

    inline int Delete(int x);

    inline int Rank(int x);

    inline int Query(int x);

    inline int Precursor(int x);

    inline int Successor(int x);

};

noneRotateTreap NoneRotateTreap;

int main()

{

    srand((unsigned long long)"非旋treap呀");

    int n, Opt, x;

    scanf("%d", &n);

    for (; n; --n)

    {

        scanf("%d%d", &Opt, &x);

        switch (Opt)

        {

        case 1:

            NoneRotateTreap.Insert(x);

            break;

        case 2:

            NoneRotateTreap.Delete(x);

            break;

        case 3:

            printf("%d\n", NoneRotateTreap.Rank(x));

            break;

        case 4:

            printf("%d\n", NoneRotateTreap.Query(x));

            break;

        case 5:

            printf("%d\n", NoneRotateTreap.Precursor(x));

            break;

        case 6:

            printf("%d\n", NoneRotateTreap.Successor(x));

        default:

            break;

        }

    }

    return 0;

}

inline void node::Update()

{

    Size = Count;

    if (LeftChild != NULL)

        Size += LeftChild->Size;

    if (RightChild != NULL)

        Size += RightChild->Size;

    return;

}

inline std::pair<node *, node *> noneRotateTreap::Split(node *Rt, int x)

{

    if (Rt == NULL)

        return std::pair<node *, node *>(NULL, NULL);

    if (x < Rt->Value)

    {

        std::pair<node *, node *> Temp = Split(Rt->LeftChild, x);

        Rt->LeftChild = Temp.second;

        Rt->Update();

        return std::pair<node *, node *>(Temp.first, Rt);

    }

    else

    {

        std::pair<node *, node *> Temp = Split(Rt->RightChild, x);

        Rt->RightChild = Temp.first;

        Rt->Update();

        return std::pair<node *, node *>(Rt, Temp.second);

    }

}

inline node *noneRotateTreap::Merge(node *l, node *r)

{

    if (l == NULL)

        return r;

    if (r == NULL)

        return l;

    if (l->Priority <= r->Priority)

    {

        l->RightChild = Merge(l->RightChild, r);

        l->Update();

        return l;

    }

    else

    {

        r->LeftChild = Merge(l, r->LeftChild);

        r->Update();

        return r;

    }

}

inline node *noneRotateTreap::Find(int x)

{

    node *Rt = Root;

    while (Rt)

    {

        if (Rt->Value == x)

            return Rt;

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return NULL;

}

inline void noneRotateTreap::Update(int x, int State)

{

    node *Rt = Root;

    while (Rt)

    {

        Rt->Size += State;

        if (Rt->Value == x)

        {

            Rt->Count += State;

            return;

        }

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return;

}

inline void noneRotateTreap::Insert(int x)

{

    node *T = Find(x);

    if (T != NULL)

    {

        Update(x, 1);

        return;

    }

    std::pair<node *, node *> Temp = Split(Root, x);

    Temp.first = Merge(Temp.first, new node(x));

    Root = Merge(Temp.first, Temp.second);

    return;

}

inline int noneRotateTreap::Delete(int x)

{

    node *T = Find(x);

    if (T == NULL)

        return 1;

    if (T->Count > 1)

    {

        Update(x, -1);

        return 0;

    }

    std::pair<node *, node *> Temp1 = Split(Root, x - 1);

    std::pair<node *, node *> Temp2 = Split(Temp1.second, x);

    delete Temp2.first;

    Root = Merge(Temp1.first, Temp2.second);

    return 0;

}

#define LCS (Rt->LeftChild ? Rt->LeftChild->Size : 0)

inline int noneRotateTreap::Rank(int x)

{

    node *Rt = Root;

    int Ans = 0;

    while (Rt)

    {

        if (Rt->Value == x)

            return Ans + LCS + 1;

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Ans += LCS + Rt->Count, Rt = Rt->RightChild;

    }

    return Ans;

}

inline int noneRotateTreap::Query(int x)

{

    node *Rt = Root;

    while (Rt)

    {

        if (LCS < x && x <= LCS + Rt->Count)

            return Rt->Value;

        if (x <= LCS)

            Rt = Rt->LeftChild;

        else

            x -= LCS + Rt->Count, Rt = Rt->RightChild;

    }

    return 0;

}

#undef LCS

inline int noneRotateTreap::Precursor(int x)

{

    int Ans = INF;

    node *Rt = Root;

    while (Rt)

    {

        if (Rt->Value < x)

            Ans = Rt->Value, Rt = Rt->RightChild;

        else

            Rt = Rt->LeftChild;

    }

    return Ans;

}

inline int noneRotateTreap::Successor(int x)

{

    int Ans = -INF;

    node *Rt = Root;

    while (Rt)

    {

        if (Rt->Value > x)

            Ans = Rt->Value, Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return Ans;

}

巴特西

非旋treap

核心思想

核心操作

其他操作

参考程序

最新文章

热门文章