P5076. 普通二叉树（简化版）

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 平衡树

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e4 + 50;
int tot;
struct Node
{
    //lc_: 左孩子下标
    //rc_: 右孩子下标
    //size_: 以当前结点为根结点时，左右子树的结点个数和(包括本身的个数num_)
    //value_: 结点的权值
    //num_: 当前结点权值出现的次数
    int lc_, rc_, size_, value_, num_;
    Node(int lc = 0, int rc = 0, int size = 0, int value = 0, int num = 1) : lc_(lc), rc_(rc), size_(size), value_(value), num_(num) {}
} tree[LEN];

#define rt tree[root]
#define lc tree[tree[root].lc_]
#define rc tree[tree[root].rc_]

//更新沿途的结点信息
void update(int root)
{
    rt.size_ = lc.size_ + rc.size_ + rt.num_;
}

//查找数的排名
int rk(int x, int root)
{
    //若找不到，返回第一个大于x的数的排名
    if (!root)
        return 1;
    //小于当前根结点值，向左子树找
    if (x < rt.value_)
        return rk(x, rt.lc_);
    //大于当前根结点值，向右子树找
    else if (x > rt.value_)
        return lc.size_ + rt.num_ + rk(x, rt.rc_);
    else
        return lc.size_ + 1;
}

//查询排名为x的数
int kth(int x, int root)
{
    //排名x的数在左子树
    if (x <= lc.size_)
        return kth(x, rt.lc_);
    //当前根结点就是排名为x的数
    else if (x <= lc.size_ + rt.num_)
        return rt.value_;
    else
        return kth(x - lc.size_ - rt.num_, rt.rc_);
}

//插入数x
void insert(int x, int root)
{
    //x在左子树
    if (x < rt.value_)
    {
        //如果左子树存在，继续递归
        if (rt.lc_)
            insert(x, rt.lc_);
        else
            tree[rt.lc_ = ++tot] = Node(0, 0, 1, x);//不存在则新建左孩子
    }
    else if (x > rt.value_)
    {
        if (rt.rc_)
            insert(x, rt.rc_);
        else
            tree[rt.rc_ = ++tot] = Node(0, 0, 1, x);
    }
    else
        ++rt.num_;
    update(root);
}

int main()
{
    int q, root, opt, x;
    cin >> q;
    tree[root = ++tot] = Node(0, 0, 1, 2147483647);
    while (q--)
    {
        cin >> opt >> x;
        switch (opt)
        {
        case 1:
            cout << rk(x, root) << endl;
            break;
        case 2:
            cout << kth(x, root) << endl;
            break;
        case 3:
        {
            int nth = rk(x, root) - 1;
            if (nth == 0)
                cout << -2147483647 << endl;
            else
                cout << kth(nth, root) << endl;
            break;
        }
        case 4:
            cout << kth(rk(x + 1, root), root) << endl;
            break;
        case 5:
            insert(x, root);
            break;
        }
    }
    return 0;
}

思路

本题是BST二叉搜索树的模板题，BST本身并没有应用空间，基本都是在用Splay、Treap、红黑树等平衡树

但手敲BST之后能对后续的平衡树学习有极大的帮助

具体实现细节见代码，主要讲一下实现难点

编程设计

查询x数的排名

每次将x和根结点root的权值比较：

  • 如果x小于根结点root的权值，那么root及其右子树里面的所有权值都比x要大，所以递归下去查询左子树

  • 如果x大于根结点root的权值，那么root及其左子树里面的所有权值都比x要小，所以递归下去查找右子树

    并且把左子树的大小及根结点的权值出现次数纳入到答案中

  • 如果x等于根结点root的权值，答案就等于左子树大小 + 1

  • 如果x不存在，返回第一个大于x的数的排名

比如数据{1, 2, 3, 3, 5}

查询0，应返回1

查询3，应返回3

查询5，应返回5

查询6，应返回6

查询排名为x的数

  • 如果x小于或等于左子树的大小，则数必在左子树当中，递归查询左子树
  • 如果x大于左子树的大小但小于等于左子树大小 + 根结点权值出现次数，说明根结点的权值就是该数
  • 若大于左子树大小 + 根结点权值出现次数，说明在右子树；则减去左子树大小 + 根结点权值出现次数后递归查询右子树

插入

找合适的位置插入即可，不再赘述

前驱与后继

这才是本题的核心坑点

根据题眼未找到前驱输出−2147483647，未找到后驱输出2147483647，实际上就是数列中的极小值和极大值...

找数的排名时，若该数不存在则返回第一个大于该数的排名；可以插入一个结点，令其权值设为极大值

比如{1, 2}查找数字3，得到的结果是3，但是数列并没有3；直接插入极大值{1, 2, 2147483647}解决

可以直接插入极小值吗？不可以！因为排名是根据左子树大小来计算的，插入极小值左子树大小会变更

考虑到唯一没有前驱的时候，就是求第一元素的前驱...所以特判即可处理

怎么求前驱呢？先求该数的排名nth，再去找排名等于nth - 1的数即可

题目说了，排名定义为比当前数小的数的个数+1

无论该数有多少个重复，都只取该数的第一个的排名作为答案

若该数不存在，也是返回第一个大于该数的排名

两种情况下，排名减去1都是前驱的排名

怎么求后驱呢？不能像前驱那样，会受重复数的影响

比如有例子{1, 3, 3, 4, 4, 5}

查找3，排名为2

查找4，排名为4

如果找排名为3的数，答案是3而不是4

应该去找x + 1的数的排名，再通过这个排名去找数，才能得到后继

还是那个性质，若该数不存在，返回第一个大于该数的排名

比如有例子{1, 3, 3, 4, 4, 7}

要找4的后继，就先去找5的排名

但是5不存在，返回排名6

再去找排名6的数，得到真正的后继数字7