splay树的插入、查找、删除操作

Question

#include<stdio.h>
#pragma comment(linker, "/STACK:1073741824")

const int null = 0;
const int maxm = 100001;
int m_count;  //表示当前在处理第几个操作。 

/* 以下五个数组用来存splay 树。numNodes是附加信息：用来存子树的节点数，方便执行Get和Rank操作 */
int parent[maxm];    //父亲
int lchild[maxm];    //左孩子
int rchild[maxm];    //右孩子
int val[maxm];        //数据
int numNodes[maxm];    //以该点为根的结点个数

int splay[maxm]; //记录每次操作splay的次数.即输出的第2行。 

int m, root = null, count = 0;//count为最新节点的序号。 

inline void update(int x) {  //更新结点数
    numNodes[x] = numNodes[lchild[x]] + numNodes[rchild[x]] + 1;
}

void splayTree(int x) {
    int f = parent[x];
    if (f == null) return;
    splay[m_count]++; //第m_count次的splay的次数
    
    int g = parent[f];
    if (g == null) { /*zig or zag*/
        if (lchild[f] == x) { /*zig*/
            if(rchild[x]!=null){
            lchild[f] = rchild[x];
            parent[rchild[x]] = f;
            }
            else {
                lchild[f]=null;
            }
            rchild[x] = f;
            parent[f]=x;
        }
        else {                /*zag*/
            if(lchild[x]!=null){
            rchild[f] = lchild[x];
            parent[lchild[x]] = f;
            }
            else {
                rchild[f]=null;
            }
            lchild[x] = f;
            parent[f]=x;
        }
        update(f); update(x);
        parent[x] = null; root = x;
        return; 
    }
    int h=parent[g];
    if (lchild[g] == f && lchild[f] == x) {            /*zig-zig*/
        if(rchild[f]!=null){
            lchild[g] = rchild[f];
            parent[rchild[f]] = g;
        }
        else {
            lchild[g] =null;
        }
        rchild[f] = g;
        parent[g]=f;
        if (rchild[x] != null) {
        lchild[f]=rchild[x];
        parent[rchild[x]]=f;
        }
        else {
            lchild[f]=NULL;
        }
        rchild[x]=f;
        parent[f]=x;
    }
    else if (rchild[g] == f && rchild[f] == x) {    /*zag-zag*/
    if(lchild[f]!=null){
            rchild[g] = lchild[f];
            parent[lchild[f]] = g;
        }
        else {
            rchild[g] =null;
        }
        lchild[f] = g;
        parent[g]=f;
        if (lchild[x] != null) {
        rchild[f]=lchild[x];
        parent[lchild[x]]=f;
        }
        else {
            rchild[f]=NULL;
        }
        lchild[x]=f;
        parent[f]=x;
    }
    else if (lchild[g] == f && rchild[f] == x) {    /*zig-zag*/
        if(lchild[x]!=null){
            rchild[f]=lchild[x];
            parent[lchild[x]]=f;
        }
        else {
            rchild[f]=null;
        }
        lchild[x]=f;
        parent[f]=x;
        if(rchild[x]!=null){
            lchild[g]=rchild[x];
            parent[rchild[x]]=g;
        }
        else {
            lchild[g]=null;
        }
        rchild[x]=g;
        parent[g]=x;
    }
    else if (rchild[g] == f && lchild[f] == x) {    /*zag-zig*/
            if(rchild[x]!=null){
            lchild[f]=rchild[x];
            parent[rchild[x]]=f;
        }
        else {
            lchild[f]=null;
        }
        rchild[x]=f;
        parent[f]=x;
        if(lchild[x]!=null){
            rchild[g]=rchild[x];
            parent[lchild[x]]=g;
        }
        else {
            rchild[g]=null;
        }
        lchild[x]=g;
        parent[g]=x;
    }

    update(g); update(f); update(x);
    if (h == null) {
        root = x; parent[root] = null;  //更新根节点
    }
    else{
        parent[x] = h;
        if (val[x] < val[h]) lchild[h] = x;
        else {
            rchild[h] = x;
        }
        splayTree(x);
    }
}

int search(int x){ //调用search时确保root!=null 
    int p = root;
    while (val[p] != x) {
        if (x < val[p]){
            p = lchild[p];
        }
        else{
            p = rchild[p];
        }
    }
    return p; 
}

void Insert(int x) {
    count++; numNodes[count]++;
    val[count] = x; //创建结点，count为其索引
    lchild[count] = rchild[count] = null;
    if (root == null) {   //根节点为空
        root = count; parent[root] = null;
     }
    else { 
    int p = root;
        while (true) {
            if (x < val[p]) {
                if (lchild[p] == null) {
                    lchild[p] = count;
                    break;
                } else {
                    p = lchild[p];
                }
            } else {
                if (rchild[p] == null) {
                    rchild[p] = count;
                    break;
                } else {
                    p = rchild[p];
                }
            }
        }
        parent[count] = p;
        splayTree(count);
    }
}

void Delete(int p){
    if (lchild[p] != null && rchild[p] != null) {  //待删除节点2个孩子 
        int s = lchild[p];
        while (rchild[s] != null) s = rchild[s];
        //add sth here.  //此时待删除节点变为了s。f仍然是p的父亲。 p只有<=1个孩子了。
          if (lchild[s] != null) {
            parent[lchild[s]] = p;  // 将s的左子树的父亲指向p
            lchild[p] = lchild[s];   // 将p的左子树改为s的左子树
        }

        // 删除节点s
        if (s != lchild[p]) {
            parent[rchild[s]] = s;  // 如果s不是p的左孩子，则把s的右子树接到s的父节点
            rchild[s] = rchild[p];   // 将p的右子树挂到s上
        }
        
        // 删除节点p之后，s变为新的p，并且做相应的旋转调整
        splayTree(s);
        return;
    }
    int f = parent[p], s = lchild[p] != null ? lchild[p] : rchild[p]; // s是空或是p的唯一的孩子孩子 
    if (f == null) { /*删除的节点p是根节点*/
        root = s; parent[root] = null;
    }
    else{
         if (lchild[f] == p) {
            lchild[f] = s;  // 将父节点的左子树指向s
        } else {
            rchild[f] = s;  // 将父节点的右子树指向s
        }
        if (s != null) {
            parent[s] = f;  // 将s的父亲设置为f
        }
    }
    splayTree(s);
}

int Rank(int x) {
    int q = root;
    int cnt = 0; 
    while (true) {
        int n = numNodes[lchild[q]];
        if (x > val[q]) {
            cnt += n + 1;
            q = rchild[q];
        }
        else if (x < val[q])
            q = lchild[q];
        else{
            cnt += n + 1;
            break;
        }
    }
}

int Get(int k) {//找第k小的数 
    int q = root;
    while (true) {
        int n = numNodes[lchild[q]];
        if (k > n + 1) {
            k -= n + 1;
            q = rchild[q];
        }
        else if (k <= n) {
            q = lchild[q];
        } 
        else {
            return val[q];
        }
    }
}

int result[maxm];

int main() {
    int kind, x, t_rank_get = 0;//kind表示操作类型  x表示操作参数
    scanf("%d", &m);
    for (m_count = 1; m_count <= m; m_count++) {
        scanf("%d %d", &kind, &x);
        if (1 == kind) Insert(x);
        else if (2 == kind) Delete(search(x));
        else if (3 == kind) result[++t_rank_get] = Rank(x);
        else result[++t_rank_get] = Get(x);
    }
    for (int i = 1; i <= t_rank_get; i++) printf("%d ", result[i]);
    printf("\n");
    for (int i = 1; i <= m; i++) printf("%d ", splay[i]);
    return 0;
}

预计输入：
10
1 1
1 2
1 3
1 4
1 5
1 6
2 1
3 3
4 5
2 5
输出：
2 6
0 1 1 1 1 1 2 1 1 0
但是上述代码输出：
3 5
0 1 1 1 1 1 0 0 0 1
该代码有什么逻辑问题？

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

经过对您的代码进行审查，我发现了几个潜在的问题。我将按照问题的严重性逐一列出并给出相应的修复建议。

问题一：在删除节点时，您的代码逻辑可能存在问题。在删除节点后，您应该重新平衡树以保持树的性质。您的代码似乎没有正确处理所有的平衡情况。一种可能的问题场景是，在删除节点后，树的形状可能会改变，某些节点的子节点可能会发生变化，这可能导致不正确的旋转操作。因此，您需要确保在删除节点后正确地更新树的结构。

问题二：在查找节点时，您假设根节点始终存在（root != null）。然而，在某些情况下（例如删除所有节点后），根节点可能为空，这可能导致未定义的行为。您应该在调用search函数之前检查根节点是否为空。

问题三：在Get函数中，当找到目标节点时，您应该返回该节点的值（val[q]），而不是节点的索引（q）。这将使您能够得到正确的结果。

问题四：在主函数中，使用变量t_rank_get来存储结果数组的下标可能不是一个好的选择。因为每次调用Get或Rank函数时都会增加t_rank_get的值，这可能导致不正确的索引。更好的做法是直接将结果存储在一个数组中，并在每次调用Get或Rank函数时将结果赋值给该数组。这样可以确保每个操作的输出都是独立的。

针对上述问题，我建议您对代码进行以下修改：

1. 在删除节点后重新平衡树的结构，确保树的性质得到维护。这可能涉及到更复杂的逻辑和额外的辅助函数来处理各种平衡情况。
2. 在调用search函数之前检查根节点是否为空。如果根节点为空，可以采取适当的处理措施，例如输出错误消息或执行其他逻辑操作。
3. 在Get函数中返回节点的值而不是节点的索引。确保正确返回节点的值。
4. 在主函数中修复Get和Rank函数的返回值存储问题。使用一个独立的结果数组来存储每个操作的输出，并确保将结果正确地赋值给数组的每个位置。以下是一些伪代码片段来说明上述修复措施的一部分实现：

修复后的部分代码示例：

// ... 其他代码保持不变 ...

int Get(int k) { // 找第k小的数 
    int q = root;
    while (true) { // 确保根节点不为空后再进行操作
        if (root == null) return -1; // 返回错误标识或抛出异常等处理措施
        int n = numNodes[lchild[q]]; // 获取左子树的节点数作为参考依据进行查找操作 ...
        // ... 其他代码逻辑不变 ... 返回到的是节点的值而不是索引 ...
    }
} // 确保返回正确的节点值而不是索引值 ...
```在主函数中修复结果存储问题：假设修复后的Get和Rank函数都返回一个结果而不是将结果存储在结果数组中。在每次调用这些函数时分配一个独立的结果变量来存储输出。然后可以将结果变量存储在适当的位置中，而不是依赖于全局变量或静态变量来跟踪结果数组的下标。请注意这些伪代码仅作为参考，实际实现需要根据具体情况进行调整和优化以确保逻辑的正确性。最后需要注意的是确保处理空根节点的情况以及更新数据结构后的平衡性是您修改的关键点。此外根据您的需求进行调整和优化也是非常重要的步骤以确保代码的健壮性和效率。