Treap树堆【东北大学oj数据结构8-4】C++

题面

二叉搜索树会因为插入的数据的值可能变得不平衡，搜索/插入/删除操作的效率变得低效。例如，如果依次插入 n 个升序的数据，则树将看起来像一个列表，其高度将为 n，并且查询时间变得很长。一个解决策略是随意打乱要插入的数据。但是我们应该思考当二叉树根据需求依次执行不同的操作的时候如何去保持二叉树的平衡。

我们可以通过给每个结点任意赋予一个优先度并且以此作为排序的依据来保持二叉树的平衡。

我们可以通过为二叉树的每个节点分配随机选择的priority并对节点进行排序来维护平衡二叉树：这里假设每个节点的key和priority都是唯一的。

• 二叉搜索树属性：如果v是u的左孩子，则v.key < u.key，如果v是u的右孩子，则u.key < v.key。
• 堆属性： 如果v 是 u 的孩子，则 v.priority < u.priority

由于二叉搜索树和堆的特性，这样的树被称为Treap（树+堆）

创建一个程序，根据上述算法为 Treap T 执行以下指令。

insert(k, p)：将一个key为k、优先级为p的元素插入到T中。
find (k)：报告 T 中是否存在key k。
delete (k)：删除key为 k 的节点。
print()：使用中序树遍历和先序树遍历算法打印key。

下图显示了Treap的一个示例。

插入
将新元素插入到Treap中，首先，插入一个随机分配priority后的节点。例如，下图显示了插入key为6且priority为90的节点后的Treap。

很明显，这个Treap违反了heap属性，因此我们需要通过旋转操作修改树的结构。旋转操作是在维护二进制搜索树属性的同时更改父子关系。

旋转操作可以按如下方式实现。

rightRotate(Node t)
    Node s = t.left
    t.left = s.right
    s.right = t
    return s // the new root of subtree

leftRotate(Node t)
    Node s = t.right
    t.right = s.left
    s.left = t
    return s // the new root of subtree 

下图显示了插入操作后的旋转操作过程，以保持正确的堆和二叉树属性。

插入操作和旋转操作可以按如下方式实现。

insert(Node t, int key, int priority)            // search the corresponding place recursively
    if t == NIL
        return Node(key, priority)               // create a new node when you reach a leaf
    if key == t.key
        return t                                 // ignore duplicated keys

    if key < t.key                               // move to the left child
        t.left = insert(t.left, key, priority)   // update the pointer to the left child
        if t.priority < t.left.priority          // rotate right if the left child has higher priority
            t = rightRotate(t)
    else                                         // move to the right child
        t.right = insert(t.right, key, priority) // update the pointer to the right child
        if t.priority < t.right.priority         // rotate left if the right child has higher priority
            t = leftRotate(t)

  return t

删除

要从Treap中删除节点，首先，应通过旋转操作移动目标节点，直到其成为叶子。然后删除节点（叶）。这些过程可以按如下方式实现。

delete(Node t, int key)                        // seach the target recursively
    if t == NIL
        return NIL
    if key < t.key                             // search the target recursively
        t.left = delete(t.left, key)
    else if key > t.key
        t.right = delete(t.right, key)
    else
        return _delete(t, key)
    return t

_delete(Node t, int key)                       // if t is the target node
    if t.left == NIL && t.right == NIL         // if t is a leaf
        return NIL
    else if t.left == NIL                      // if t has only the right child, then perform left rotate
        t = leftRotate(t)
    else if t.right == NIL                     // if t has only the left child, then perform right rotate
        t = rightRotate(t)
    else                                       // if t has both the left and right child
        if t.left.priority > t.right.priority  // pull up the child with higher priority
            t = rightRotate(t)
        else
            t = leftRotate(t)
    return delete(t, key)

基于上述算法，编写一个程序，对Treap T执行以下操作：

• insert (k, p): Insert a node containing k as key and p as priority to TT.
• find (k): Report whether T has a node containing k.
• delete (k）: Delete a node containing k.
• print(): Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.

输入

输入的第一行给出了指令数 m。 在接下来的 m 行，指令以插入 k p、查找 k、删除 k 或打印的形式给出。

输出

对于每个 find k 指令，如果 T 包含 k 则输出 yes，如果 T 不包含则输出 no。

进一步，对于每条打印指令，将中序遍历算法和前序遍历算法得到的key的排列输出到一行。 在每个键之前打印一个空格。

约束

指令数不超过20万条。
0 ≤ k, p ≤ 2,000,000,000
如果按照上面的算法，树的高度不会超过50。
二叉搜索树中的key没有重复。
二叉搜索树中没有重复的priority。
打印指令数量不超过10条。
输出的大小不超过 10 MB。

输入样例

16
insert 35 99
insert 3 80
insert 1 53
insert 14 25
insert 80 76
insert 42 3
insert 86 47
insert 21 12
insert 7 10
insert 6 90
print
find 21
find 22
delete 35
delete 99
print

输出样例

1 3 6 7 14 21 35 42 80 86
 35 6 3 1 14 7 21 80 42 86
yes
no
 1 3 6 7 14 21 42 80 86
 6 3 1 80 14 7 21 42 86 

代码实现 

#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;
 
// 定义树的节点结构
struct Node {
    int key;
    int pri;
    Node* right;
    Node* left;
    Node* p;
};
 
Node* creat(int a,int b)
{
    Node* n=new Node();
    n->key=a;
    n->pri=b;
    n->left=nullptr;
    n->right=nullptr;
    n->p=nullptr;
    return n;
}
 
Node* rightRotate(Node* t)
{
    Node* s=t->left;
    t->left=s->right;
    if(s->right!=nullptr)
        s->right->p=t;
    s->right=t;
    s->p=t->p;
    t->p=s;
    return s;
}
Node* leftRotate(Node* t)
{
    Node* s=t->right;
    t->right=s->left;
    if(s->left!=nullptr)
        s->left->p=t;
    s->left=t;
    s->p=t->p;
    t->p=s;
    return s;
}
Node* insertt(Node* t,int key,int pri)
{
    if(t==nullptr)
        return creat(key,pri);
    if(key==t->key)
        return t;
    if(key<t->key)
    {
        t->left=insertt(t->left,key,pri);
        if(t->pri<t->left->pri)
            t=rightRotate(t);
    }
    else
    {
        t->right=insertt(t->right,key,pri);
        if(t->pri<t->right->pri)
        {
                t=leftRotate(t);
        }
    }
    return t;
}
 
Node* findd(Node* root,int k)
{
    while(root!=nullptr&&k!=root->key)
    {
        if(k<root->key)
            root=root->left;
        else
            root=root->right;
    }
    return root;
}
 
Node* deletee(Node* t,int key);
Node* delett(Node* t,int key)
{
    if(t==nullptr)
        return nullptr;
    if(key<t->key)
        t->left=delett(t->left,key);
    else if(key>t->key)
        t->right=delett(t->right,key);
    else
        return deletee(t,key);
    return t;
}
Node* deletee(Node* t,int key)
{
    if(t==nullptr) return nullptr;
    if(t->left==nullptr&&t->right==nullptr)
     {
         delete t;
         return nullptr;
     }
    else if(t->left==nullptr)
        t=leftRotate(t);
    else if(t->right==nullptr)
        t=rightRotate(t);
    else
    {
        if(t->left->pri>t->right->pri)
            t=rightRotate(t);
        else
            t=leftRotate(t);
    }
    return delett(t,key);
}
 
 
void preorder(Node* a)
{
    if(a==nullptr) return;
    cout<<a->key<<" ";
    preorder(a->left);
    preorder(a->right);
}
void inorder(Node* a)
{
    if(a==nullptr) return;
    inorder(a->left);
    cout<<a->key<<" ";
    inorder(a->right);
}
 
int main() {
    int n;
    Node* tree=nullptr;
    cin>>n;
    for (int i = 0; i < n; i++) {
        string c;
        cin>>c;
        if(c=="insert")
        {
            int v,w;
            cin>>v>>w;
            tree=insertt(tree,v,w);
        }
        if(c=="find")
        {
            int v;
            cin>>v;
            Node* a=findd(tree,v);
            if(a)
                cout<<"yes"<<endl;
            else
                cout<<"no"<<endl;
        }
        if(c=="delete")
        {
            int v;
            cin>>v;
            tree=delett(tree,v);
        }
        if(c=="print")
        {
            inorder(tree);
            cout<<endl;
            preorder(tree);
            cout<<endl;
        }
    }
    return 0;
}