宏定义目录Macro Index#

把可能会用到的宏定义函数放在开头：

基本结构Basic Structure Definition#

我们知道二叉树是可能会有左右子节点的，因此需要设计两个变量存储左右子节点 的下标；点的权值也是我们需要关心的；为了应对可能出现的权值重复，我们可以考虑加入一个权值计数，让相同权值的点不会被加入两次；最后为了应对一些题目的要求，维护一个记录子树总点数的变量。结构体看起来大概是这样的：

1
struct BST {
2
// Some macro definitions, see the table above
3
#define leftSubtree(idx) (tree[tree[idx].ls])
4
#define rightSubtree(idx) (tree[tree[idx].rs])
5
#define NEGAINF_NODE 2
6
#define POSIINF_NODE 1
7
    int ls, rs; // Index for left/right sons
8
    int dat;    // Data carried by the node or simply a node value
9
    int cnt;    // Count in case there's a duplicated value
10
    int size;   // Total child nodes
11
} tree[N];
12
int root;       // Record the root node index, normally it's 1

建树&单点创建Build & Node Allocating #

写 有一个不成文的规矩：在建树时加入两个边界节点正无穷和负无穷，其中一个作为树的根节点，选哪个都可以。我选择将正无穷作为根节点，根据定义，负无穷节点应是它的左儿子。特别地，我们称只包含正/负无穷节点的 为空。因此建树只需创建两个无穷节点即可，注意对于初始建立的无穷权节点，实际上是不会包含在 中的，因此设立一个特判，将它们的重复计数设为 ，否则在计算排名时会出错。

接下来就是单点的创建了。在 中，我们使用类似于链式前向星的方法创建某个点。关键代码如下：

1
int idx = 0, root;
2

3
int allocate(int dat, bool on_init = false) {
4
    idx++;
5
    tree[idx].dat = dat;
6
    tree[idx].cnt = (on_init) ? 0 : 1;     // Process duplication count with special judge
7
    tree[idx].size = 1;                    // Add to subnode count
8
    return idx;
9
}
10

11
void build() {
12
    allocate(INF);
13
    allocate(-INF);
14
    root = 1;           // Take the first node as root. It's positive infinity
15
    tree[1].ls = 2;     // According to the passage, negative infinity should be the left son
16
}

为 allocate() 函数设返回值大概是它与链式前向星最大的区别点了，后文会讲到设返回值的妙用。

单点查询Index Query#

根据开头介绍的 的性质，写这个就非常简单了。主要分以下几个情况考虑（假设目标值为 ，当前值为 ，不保证是否存在该权值）：

1. 若 ，即查询到目标节点，返回下标
2. 若 ，向左子树递归搜索
3. 若 ，向右子树递归搜索
4. 若下标无意义，返回不存在（表现在下标为 ）

1
int query(int idx, int dat) {
2
    if (!idx) return 0;                                            // Nonsense index indicates failure
3
    if (dat == tree[idx].dat) return idx;                           // Found!
4
    if (dat > tree[idx].dat) return query(tree[idx].rs, dat);   // Target is greater than current, recurse to right son
5
    return query(tree[idx].ls, dat);                            // Recurse to left son
6
}

插入数值Value Insertion#

注意：这和前文所述的单点创建并不等价。在这一操作中，我们需要关注已有的其他点的权值情况。在 中，是不能出现两个不同的点（下标不同）共享同一份权值的。虽然很多题目会明确指出“本题数据保证不存在权值相同的两个点”，但有时也会出现例外。对于这类例外的题目，前面设立的变量就有用武之地了！

理论上我们可以通过调用 query() 函数来快捷得知该权值的存在性，但是实践时一般不采用这种做法。考虑到先前所讲的几大函数都没有对节点之间的从属关系进行更新，又因为插入操作会涉及到节点之间的关系转换，故将更新左右儿子的操作放在此处。

首先还是需要获取该权值理应存放的位置，求解策略跟单点查询相同。只是我们将递归参数“下标”设为引用形式，这样在一层层向上返回时就可以顺便更新父节点的左右儿子下标了。此时单点创建函数的返回值将作为新建点的序号向上传递，一路更新至根节点。

1
void insert(int &idx, int dat) {
2
    if (!idx) {
3
        idx = allocate(dat); // Does not exist, then allocate a new node
4
        return;
5
    }
6
    if (tree[idx].dat == dat) {
7
        tree[idx].cnt++;     // Encounter a duplicated node, add to its count
8
        return;
9
    }
10
    if (tree[idx].dat < dat) insert(tree[idx].rs, dat);
11
    if (tree[idx].dat > dat) insert(tree[idx].ls, dat);
12
    tree[idx].size = (tree[idx].ls ? leftSubtree(idx).size : 0) + (tree[idx].rs ? rightSubtree(idx).size : 0) + tree[idx].cnt;        // Recursivly update the tree size
13
}

前驱&后继Precursor & Successor Node#

前驱Precursor Node：在所有权值小于当前点权的点之中，权值最大的那一个。

后继Successor Node：在所有权值大于当前点权的点之中，权值最小的那一个。

以求前驱为例（如果权值是给定值的点不存在，我们默认它的前驱是负无穷）：首先我们需要从根节点开始，向下找到给定权值应该存放的位置。如果找到权值是给定值的点，要保证答案点的权值小于基准点，我们就要先向左子树走（树内权值均小于父节点），接着一直沿右子树（树内权值均大于父节点）走到底即可找到前驱。求后继类似，只是需要先找到基准点的右子树，然后一直沿左子树走到底。

因为查询排名和查询数值都有一步查找对应点的步骤，与查找前驱后继的过程相同，故而可以把二者合一以简化代码（见后文）。

1
int precursor(int idx, int dat) {
2
    int res = NEGAINF_NODE; // Negative infinity
3
    while (idx) {
4
        if (tree[idx].dat == dat) {
5
            if (tree[idx].ls) { // Ensure that its left subtree exists
6
                res = tree[idx].ls;
7
                while (tree[idx].rs) res = tree[res].rs;
8
            }
9
            break;
10
        }
11
        if (tree[idx].dat < dat && tree[res].dat < tree[idx].dat) res = idx;
12
        idx = (dat > tree[idx].dat) ? tree[idx].rs : tree[idx].ls;
13
    }
14
    return res;
15
}
16

17
int successor(int idx, int dat) {
18
    int res = POSIINF_NODE; // Positive infinity
19
    while (idx) {
20
        if (tree[idx].dat == dat) {
21
            if (tree[idx].rs) {
22
                res = tree[idx].rs;
23
                while (tree[idx].ls) res = tree[idx].ls;
24
            }
25
            break;
26
        }
27
        if (tree[idx].dat > dat && tree[res].dat > tree[idx].dat) res = idx;
28
        idx = (dat > tree[idx].dat) ? tree[idx].rs : tree[idx].ls;
29
    }
30
    return res;
31
}

单点删除Node Deletion#

在一棵合法的 中，任意节点的子树也都是一棵合法的 ，这启示我们不能鲁莽、暴力地删点，而是要好好理清楚节点之间的关系之后，进行一系列操作，最后删除掉这个节点。

对于某个节点，它可能有如下几种情况：

1. 它是一个叶子节点，可以直接删除。
2. 它在一条链上（只有一个子节点）：删除这个点，同时让它的子节点代替它。
3. 它是一个二叉节点（两个子节点）：考虑提出一种方式把问题简化为以上两种特殊情况。首先找到前驱或者后继，因为前驱和后继均只有一个方向上的子树，简化成第二种情况。我们可以让前驱/后继替换要删除的节点，紧接着把替换过去的原节点删除即可！就好像剪贴覆盖的过程。
4. 如果这个点的重复数量大于一，则减去一个重复数。

1
void remove(int &idx, int dat) {
2
    if (!idx) return; // Does not exist
3
    if (tree[idx].dat == dat) {
4
        if (tree[idx].cnt > 1) tree[idx].cnt--; // Dupliacted, then minus one to its count
5
        else {
6
            if (!tree[idx].ls) idx = tree[idx].rs;     // No left subtree, replace it with its left subtree
7
            else if (!tree[idx].rs) idx = tree[idx].ls; // Vice versa
8
            else {
9
                int pre = precursor(idx, dat);   // Find the precursor
10
                remove(pre, tree[pre].dat);      // Remove precursor
11
                tree[pre] = tree[idx];           // Replace
12
                idx = pre;
13
            }
14
            return;
15
        }
16
    }
17
    if (tree[idx].dat > dat) remove(tree[idx].ls, dat);
18
    else remove(tree[idx].rs, dat);
19
}

排名查询Rank Query#

所谓排名，就是看有多少元素比你当前的元素大/小，所得数目加一的结果。 天生的有序性可以帮助我们高效地解决这一点。与数值查询不同，排名查询时给出的权值可能并不存在于任何点之中。我们的基本求解策略如下：

1. 如果需要向右子树扩展查找，则累加左子树大小和当前根节点的重复次数。
2. 如果当前根节点的权值等于给定权值，则累加左子树大小，并额外加一。
3. 如果需要向左子树扩展，递归返回向左子树查找的结果。

第一点很好理解：对于根节点，它的左子树所有点权都比根节点的小。此时我们需要查询的点权显然是大于当前根节点的（位于右子树），因而左子树、包括当前根节点在内的所有点都会排在目标点之前，需要累加起来。

第二点告诉我们这样一条消息：当前根节点就是目标节点，所以左子树的所有节点都排在它之前，需要累加。这个情况可以看作第一点的特殊形式，必须注意的是，这里无需再累加当前根节点的重复次数。

对于第三点：因为我们不确定左子树的情况（有大有小），因此无需多虑直接递归进去就好。

1
int getRankByData(int idx, int dat) {
2
    if (!idx) return 1;
3
    if (tree[idx].dat == dat) return (tree[idx].ls ? leftSubtree(idx).size : 0) + 1;
4
    if (tree[idx].dat < dat) return (tree[idx].ls ? leftSubtree(idx).size : 0) + getRankByData(tree[idx].rs, dat);
5
    return (tree[idx].ls ? leftSubtree(idx).size : 0) + getRankByData(tree[idx].rs, dat);
6
}

数值查询Data Query#

题目会给定一个排名，让你获取对应排名的节点权值。与上边排名查询不同的是，这里给出的排名必须有一个对应的点，因为排名是离散的、权值不离散，所以这里需要判断无解的情况。基本分五类讨论：

1. 如果左子树的大小（节点的重复数也计入）大于等于所查询的排名参数 ，向左子树递归。
2. 如果左子树的大小在如下范围内（当前根节点重复数为 ）：，返回当前根节点的权值。
3. 不在以上三类情况中，向右子树递归，参数减去左子树的大小以及当前根节点的重复数。
4. 当前下标无意义，判无解并返回。

首先，左子树是一定小于当前根节点的。如果左子树的大小都超过了排名参数，就代表目标点在左子树内，继续向左子树递归找排名为 的点即可。

对于第二点，当前根节点的重复数为 ，那么对于根节点这个大集合（相同权值记作不同排名），排名的范围就是 。因此一旦满足该关系直接返回。

最后是第三点，因为左子树的大小与根节点重复数的和小于当前排名，代表我们要找的点在右子树。在右子树中它的排名又是多少呢？显然，因为左子树和根节点占去了一部分排名，在右子树中，它的排名就需要减去这二者的和。

第四点属于无解判断，不再赘述。

1
int getDataByRank(int idx, int rank) {
2
    if (!idx) return -1;
3
    if (leftSubtree(idx).size >= rank) return getDataByRank(tree[idx].ls, rank);
4
    if (leftSubtree(idx).size + tree[idx].cnt >= rank) return tree[idx].dat;
5
    return getDataByRank(tree[idx].rs, rank - (tree[idx].ls ? leftSubtree(idx).size : 0) - tree[idx].cnt);
6
}

洛谷 P5076 [深基16.例7] 普通二叉树（简化版）#

题目地址：P5076

题目难度：普及+/提高

您需要写一种数据结构，来维护一些数（都是绝对值 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 不超过 ：

1. 定义数 的排名为集合中小于 的数的个数 。查询数 的排名。注意 不一定在集合里。
2. 查询排名为 的数。保证集合里至少有 个数。
3. 求 的前驱（前驱定义为小于 ，且最大的数）。若不存在则输出 。
4. 求 的后继（后继定义为大于 ，且最小的数）。若不存在则输出 。
5. 插入一个数 ，本题的数据保证插入前 不在集合中。

保证执行 操作时，集合中有至少一个元素。

输入格式：

第一行是一个整数 ，表示操作次数。

接下来 行，每行两个整数 ，分别表示操作序号以及操作的参数 。

输出格式：

输出有若干行。对于操作 ，输出一个整数，表示该操作的结果。

这是一道模板题，套用上边的模板即可（甚至不涉及节点删除）。为了压缩篇幅，代码放在此处。

你怎么知道我花了三节晚自习+一个上午过样例、大半个下午调代码？（因为查询数值时没判断是否是边界节点）