数据结构(荣誉)实验四 Splay伸展树

简介: 数据结构(荣誉)实验四 Splay伸展树

1. Splay —— Ver.I


题目描述


image.png


输入


第一行包含一个整数n,表示初始序列的长度。 以下n行每行包含一个整数,描述初始的序列。 接下来一行包含一个整数n,表示插入操作的数目。 以下m行每行描述一个操作。


接下来一行包含一个整数q,表示查询和删除操作的总数目,以下q行描述一个操作


输出


对于所有操作,输出正确的答案。


样例输入


5

1 2 3 4 5

3

ADD 9

ADD 10

ADD 199

5

QUERY 1

QUERY 3

DELETE 1

DELETE 3

QUERY 3


样例输出


the number is good

the number is good

2 3 4 5 9 10 199

2 4 5 9 10 199

the number is bad


题解

#include <iostream>
#include <string>
using namespace std;
struct Node
{
    struct Node *lchild;
    struct Node *rchild;
    struct Node *parent;
    int data;
    Node()
    {
        lchild = rchild = parent = NULL;
        data = 0;
    }
};
void Print(Node *root)
{
    if (root)
    {
        Print(root->lchild);
        if (root->data == 0)
        {
        }
        else
        {
            cout << root->data << ' ';
        }
        Print(root->rchild);
    }
}
void left_single_rotate(Node *&root, Node *&node)
{
    if (node == NULL)
    {
        return;
    }
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    parent->rchild = node->lchild;
    if (node->lchild)
    {
        node->lchild->parent = node->parent;
    }
    parent->parent = node;
    node->lchild = parent;
    node->parent = grandparent;
    if (grandparent)
    {
        if (grandparent->lchild == parent)
        {
            grandparent->lchild = node;
        }
        else
        {
            grandparent->rchild = node;
        }
    }
    else
    {
        root = node;
    }
}
void right_single_rotate(Node *&root, Node *&node)
{
    if (node == NULL)
    {
        return;
    }
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    parent->lchild = node->rchild;
    if (node->rchild)
    {
        node->rchild->parent = parent;
    }
    parent->parent = node;
    node->rchild = parent;
    node->parent = grandparent;
    if (grandparent)
    {
        if (grandparent->lchild == parent)
        {
            grandparent->lchild = node;
        }
        else
        {
            grandparent->rchild = node;
        }
    }
    else
    {
        root = node;
    }
}
void SplayUp(Node *&root, Node *&node)
{
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    if (grandparent->lchild == parent && parent->lchild == node)
    {
        right_single_rotate(root, node);
        right_single_rotate(root, node);
    }
    else if (parent->lchild != node && grandparent->lchild != parent)
    {
        left_single_rotate(root, node);
        left_single_rotate(root, node);
    }
    else if (grandparent->lchild == parent && parent->lchild != node)
    {
        left_single_rotate(root, node);
        right_single_rotate(root, node);
    }
    else if (grandparent->lchild != parent && parent->lchild == node)
    {
        right_single_rotate(root, node);
        left_single_rotate(root, node);
    }
}
void AddSplay(int x, Node *&root, Node *par)
{
    if (!root)
    {
        root = new Node;
        root->data = x;
        root->parent = par;
    }
    else if (x < root->data)
    {
        AddSplay(x, root->lchild, root);
    }
    else if (x > root->data)
    {
        AddSplay(x, root->rchild, root);
    }
}
void CreatSplay(int n, Node *&root)
{
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        AddSplay(temp, root, NULL);
    }
}
Node *FindLChild(Node *r)
{
    while (r->lchild)
    {
        r = r->lchild;
    }
    return r;
}
Node *FindSplay(int x, Node *&root)
{
    if (!root)
        return NULL;
    if (root->data < x)
        return FindSplay(x, root->rchild);
    else if (root->data > x)
        return FindSplay(x, root->lchild);
    return root;
}
void splay(Node *&root, Node *node)
{
    while (root->lchild != node && root->rchild != node && root != node)
        SplayUp(root, node);
    if (root->lchild == node)
        right_single_rotate(root, node);
    if (root->rchild == node)
        left_single_rotate(root, node);
}
void QuerySplay(int x, Node *&root)
{
    Node *node = FindSplay(x, root);
    if (node)
    {
        cout << "the number is good" << endl;
        splay(root, node);
    }
    else
        cout << "the number is bad" << endl;
}
bool isDel(int x, Node *&root)
{
    Node *node = FindSplay(x, root);
    if (!node)
    {
        return false;
    }
    splay(root, node);
    if (!node->rchild)
    {
        Node *tmp = root;
        root = root->lchild;
        return true;
    }
    Node *min = FindLChild(node->rchild);
    node->data = min->data;
    if (min->parent->lchild == min)
    {
        min->parent->lchild = min->rchild;
    }
    else
    {
        min->parent->rchild = min->rchild;
    }
    return true;
}
void Delete(int x, Node *&root)
{
    if (isDel(x, root))
    {
        Print(root);
        cout << endl;
    }
    else
        cout << "Failed" << endl;
}
int main()
{
    Node *splayRoot = new Node;
    int n, temp;
    cin >> n;
    CreatSplay(n, splayRoot);
    cin >> temp;
    for (int i = 0; i < temp; i++)
    {
        string ope;
        int index;
        cin >> ope >> index;
        AddSplay(index, splayRoot, NULL);
    }
    cin >> temp;
    for (int i = 0; i < temp; i++)
    {
        string ope;
        int index;
        cin >> ope >> index;
        if (ope == "QUERY")
        {
            QuerySplay(index, splayRoot);
        }
        else if (ope == "DELETE")
        {
            Delete(index, splayRoot);
        }
    }
    return 0;
}

2. 宠物收养所(Splay —— 前驱后继操作)


题目描述


最近,贝贝开了一间宠物收养所。收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物,贝贝根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养所的宠物一个特点值。


这样他就能够很方便的处理整个领养宠物的过程了,宠物收养所总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。


1. 被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。(任何两只宠物的特点值都不可能是相同的,任何两个领养者的希望领养宠物的特点值也不可能是一样的)如果有两只满足要求的宠物,即存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。


2. 收养宠物的人过多,假若到来一只被收养的宠物,那么哪个领养者能够领养它呢?能够领养它的领养者,是那个希望被领养宠物的特点值最接近该宠物特点值的领养者,如果该宠物的特点值为a,存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b,那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。


【任务描述】你得到了一年当中,领养者和被收养宠物到来收养所的情况,希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有宠物,也没有领养者。


输入


第一行为一个正整数n,n<=80000,表示一年当中来到收养所的宠物和领养者的总数。接下来的n行,按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b,其中a=0表示宠物,a=1表示领养者,b表示宠物的特点值或是领养者希望领养宠物的特点值。(同一时间呆在收养所中的,要么全是宠物,要么全是领养者,这些宠物和领养者的个数不会超过10000个)


输出


仅有一个正整数,表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。


样例输入


5

0 2

0 4

1 3

1 2

1 5


样例输出

3


题解

#include <iostream>
#define MAXLEN 80002
using namespace std;
int ans, n;
struct splaytree
{
    int a[MAXLEN], l[MAXLEN], r[MAXLEN];
    int t, tot;
    void zig(int &x)
    {
        int lc = l[x];
        l[x] = r[lc];
        r[lc] = x;
        x = lc;
    }
    void zag(int &x)
    {
        int rc = r[x];
        r[x] = l[rc];
        l[rc] = x;
        x = rc;
    }
    void splay(int &t, int x)
    {
        if (!t)
            return;
        int pl = 0, pr = 0;
        for (;;)
        {
            if (x == a[t])
                break;
            if (x < a[t] && !l[t])
                break;
            if (x > a[t] && !r[t])
                break;
            if (x < a[t])
            {
                if (x < a[l[t]] && l[l[t]])
                    zig(t);
                l[pr] = t, pr = t, t = l[t];
            }
            else
            {
                if (x > a[r[t]] && r[r[t]])
                    zag(t);
                r[pl] = t, pl = t, t = r[t];
            }
        }
        l[pr] = r[t];
        r[pl] = l[t];
        l[t] = r[0];
        r[t] = l[0];
        l[0] = r[0] = 0;
    }
    void insert(const int &x)
    {
        a[++tot] = x;
        if (!t)
        {
            t = tot;
            return;
        }
        splay(t, x);
        if (x < a[t])
        {
            l[tot] = l[t];
            l[t] = tot;
        }
        else
        {
            r[tot] = r[t];
            r[t] = tot;
        }
    }
    void suit(const int &x)
    {
        if (!t)
            return;
        splay(t, x);
        splay(l[t], a[t]);
        splay(r[t], a[t]);
        int pl = abs(a[l[t]] - x), pm = abs(a[t] - x), pr = abs(a[r[t]] - x);
        if (x < a[t] && pl <= pm && l[t])
        {
            ans += pl;
            ans %= 1000000;
            l[t] = l[l[t]];
        }
        else if (x > a[t] && pr < pm && r[t])
        {
            ans += pr;
            ans %= 1000000;
            r[t] = r[r[t]];
        }
        else
        {
            ans += pm;
            ans %= 1000000;
            if (l[t])
            {
                r[l[t]] = r[t];
                t = l[t];
            }
            else if (r[t])
            {
                l[r[t]] = l[t];
                t = r[t];
            }
            else
                t = 0;
        }
    }
} SP[2];
int main()
{
    int x, y;
    cin >> n;
    while (n--)
    {
        cin >> x >> y;
        if (SP[x].t)
        {
            SP[x].suit(y);
        }
        else
        {
            SP[!x].insert(y);
        }
    }
    cout << ans << endl;
    return 0;
}
目录
打赏
0
0
0
0
2
分享
相关文章
数据结构实验之矩阵的运算器(二维数组)
本实验旨在通过团队合作,掌握数组和矩阵相关运算的代码实现,包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中,成员们需分工协作,解决编程难题,最终实现一个功能完备的矩阵计算器。通过本实验,不仅锻炼了编程能力,还加深了对数学概念的理解,同时培养了团队合作精神。
102 4
|
5月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术,通过创建文本文件、实现单词计数与定位功能,最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单,以增强对字符串处理的理解与应用能力。
108 4
|
5月前
|
数据结构实验之最长公共子序列
本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法,以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出,`memset()`函数用于内存初始化,且对于特定输入,程序能正确输出最长公共子序列之一。
85 4
|
5月前
|
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题,掌握队列的基本操作如入队、出队等,利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能,并通过菜单式界面进行交互。实验结果显示基本功能可正常执行,但在连续操作时存在执行失败的情况,需进一步优化。
84 4
|
28天前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
41 3
 算法系列之数据结构-Huffman树
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
77 19
|
3月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
92 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
3月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
86 12
|
3月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
74 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
81 2