fixViolation方法中在while循环中出错
时间: 2024-04-16 12:28:10 浏览: 8
非常抱歉,我之前提供的代码确实有错误。在 `fixViolation` 方法中,当进行左旋或右旋操作时,需要更新相关节点的父节点指针。下面是修正后的代码:
```c
void fixViolation(struct Node **root, struct Node *node) {
struct Node *parent = NULL;
struct Node *grandparent = NULL;
while ((node != *root) && (node->color != BLACK) &&
(node->parent->color == RED)) {
parent = node->parent;
grandparent = parent->parent;
if (parent == grandparent->left) {
struct Node *uncle = grandparent->right;
if (uncle != NULL && uncle->color == RED) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
node = grandparent;
} else {
if (node == parent->right) {
rotateLeft(root, parent);
node = parent;
parent = node->parent;
}
rotateRight(root, grandparent);
int temp = parent->color;
parent->color = grandparent->color;
grandparent->color = temp;
node = parent;
}
} else {
struct Node *uncle = grandparent->left;
if ((uncle != NULL) && (uncle->color == RED)) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
node = grandparent;
} else {
if (node == parent->left) {
rotateRight(root, parent);
node = parent;
parent = node->parent;
}
rotateLeft(root, grandparent);
int temp = parent->color;
parent->color = grandparent->color;
grandparent->color = temp;
node = parent;
}
}
}
(*root)->color = BLACK;
}
void rotateLeft(struct Node **root, struct Node *node) {
struct Node *rightChild = node->right;
node->right = rightChild->left;
if (node->right != NULL)
node->right->parent = node;
rightChild->parent = node->parent;
if (node->parent == NULL)
(*root) = rightChild;
else if (node == node->parent->left)
node->parent->left = rightChild;
else
node->parent->right = rightChild;
rightChild->left = node;
node->parent = rightChild;
}
void rotateRight(struct Node **root, struct Node *node) {
struct Node *leftChild = node->left;
node->left = leftChild->right;
if (node->left != NULL)
node->left->parent = node;
leftChild->parent = node->parent;
if (node->parent == NULL)
(*root) = leftChild;
else if (node == node->parent->left)
node->parent->left = leftChild;
else
node->parent->right = leftChild;
leftChild->right = node;
node->parent = leftChild;
}
```
这些更改会更新节点的父节点指针,以确保树结构正确。请尝试使用修正后的代码,看看是否可以正确地插入和修复红黑树的违规操作。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)