社区讨论
有没有大佬看看 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 条回复,欢迎继续交流。
正在加载回复...