社区讨论

有没有大佬看看 GPT 哪里写错了,WA 52分

P3369【模板】普通平衡树参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo2wcd0u
此快照首次捕获于
2023/10/23 20:51
2 年前
此快照最后确认于
2023/10/23 20:51
2 年前
查看原帖
这份代码 52 分,由 一个类似于 ChatGPT 的网站 生成。
CPP
#include <iostream>
using namespace std;
struct Node {
    int val;
    int height;
    int size;
    Node* left;
    Node* right;
    Node(int x) : val(x), height(1), size(1), left(NULL), right(NULL) {}
};
int getHeight(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}
int getSize(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->size;
}
void updateHeight(Node* node) {
    if (node == NULL) {
        return;
    }
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}
void updateSize(Node* node) {
    if (node == NULL) {
        return;
    }
    node->size = getSize(node->left) + getSize(node->right) + 1;
}
int getBalanceFactor(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}
void leftRotation(Node* &node) {
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    updateHeight(node);
    updateHeight(temp);
    updateSize(node);
    updateSize(temp);
    node = temp;
}
void rightRotation(Node* &node) {
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    updateHeight(node);
    updateHeight(temp);
    updateSize(node);
    updateSize(temp);
    node = temp;
}
void insert(Node* &node, int val) {
    if (node == NULL) {
        node = new Node(val);
        return;
    }
    if (val < node->val) {
        insert(node->left, val);
    } else if (val > node->val) {
        insert(node->right, val);
    }
    updateHeight(node);
    updateSize(node);
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor == 2) {
        if (getBalanceFactor(node->left) == 1) {
            rightRotation(node);
        } else if (getBalanceFactor(node->left) == -1) {
            leftRotation(node->left);
            rightRotation(node);
        }
    } else if (balanceFactor == -2) {
        if (getBalanceFactor(node->right) == -1) {
            leftRotation(node);
        } else if (getBalanceFactor(node->right) == 1) {
            rightRotation(node->right);
            leftRotation(node);
        }
    }
}
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
void remove(Node* &node, int val) {
    if (node == NULL) {
        return;
    }
    if (val < node->val) {
        remove(node->left, val);
    } else if (val > node->val) {
        remove(node->right, val);
    } else {
        if (node->left == NULL && node->right == NULL) {
            node = NULL;
        } else if (node->left == NULL) {
            node = node->right;
        } else if (node->right == NULL) {
            node = node->left;
        } else {
            Node* temp = findMin(node->right);
            node->val = temp->val;
            remove(node->right, temp->val);
        }
    }
    if (node == NULL) {
        return;
    }
    updateHeight(node);
    updateSize(node);
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor == 2) {
        if (getBalanceFactor(node->left) == 1) {
            rightRotation(node);
        } else if (getBalanceFactor(node->left) == -1) {
            leftRotation(node->left);
            rightRotation(node);
        }
    } else if (balanceFactor == -2) {
        if (getBalanceFactor(node->right) == -1) {
            leftRotation(node);
        } else if (getBalanceFactor(node->right) == 1) {
            rightRotation(node->right);
            leftRotation(node);
        }
    }
}
int getRank(Node* node, int val) {
    if (node == NULL) {
        return 0;
    }
    if (val < node->val) {
        return getRank(node->left, val);
    } else if (val > node->val) {
        return getSize(node->left) + 1 + getRank(node->right, val);
    } else {
        return getSize(node->left) + 1;
    }
}
Node* getKthNode(Node* node, int k) {
    if (node == NULL) {
        return NULL;
    }
    int leftSize = getSize(node->left);
    if (k <= leftSize) {
        return getKthNode(node->left, k);
    } else if (k == leftSize + 1) {
        return node;
    } else {
        return getKthNode(node->right, k - leftSize - 1);
    }
}
int getPredecessor(Node* node, int val) {
    int rank = getRank(node, val);
    Node* kthNode = getKthNode(node, rank - 1);
    if (kthNode == NULL) {
        return -1;
    }
    return kthNode->val;
}
int getSuccessor(Node* node, int val) {
    int rank = getRank(node, val);
    Node* kthNode = getKthNode(node, rank + 1);
    if (kthNode == NULL) {
        return -1;
    }
    return kthNode->val;
}
int main() {
    Node* root = NULL;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) {
            insert(root, x);
        } else if (opt == 2) {
            remove(root, x);
        } else if (opt == 3) {
            cout << getRank(root, x) << endl;
        } else if (opt == 4) {
            Node* kthNode = getKthNode(root, x);
            if (kthNode == NULL) {
                cout << -1 << endl;
            } else {
                cout << kthNode->val << endl;
            }
        } else if (opt == 5) {
            insert(root,x);
            cout << getPredecessor(root, x) << endl;
            remove(root,x);
        } else if (opt == 6) {
            insert(root,x);
            cout << getSuccessor(root, x) << endl;
            remove(root,x);
        }
    }
    return 0;
}  

回复

4 条回复,欢迎继续交流。

正在加载回复...