提供一个红黑树实现代码
时间: 2023-03-28 16:00:30 浏览: 58
以下是一个红黑树的实现代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
int color; // 表示黑色,1 表示红色
struct Node *left;
struct Node *right;
struct Node *parent;
} Node;
Node *create_node(int val) {
Node *node = (Node *)malloc(sizeof(Node));
node->val = val;
node->color = 1; // 新插入的节点默认为红色
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
void left_rotate(Node **root, Node *x) {
Node *y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
*root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate(Node **root, Node *y) {
Node *x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
*root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}
void insert_fixup(Node **root, Node *z) {
while (z->parent != NULL && z->parent->color == 1) {
if (z->parent == z->parent->parent->left) {
Node *y = z->parent->parent->right;
if (y != NULL && y->color == 1) {
z->parent->color = ;
y->color = ;
z->parent->parent->color = 1;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
left_rotate(root, z);
}
z->parent->color = ;
z->parent->parent->color = 1;
right_rotate(root, z->parent->parent);
}
} else {
Node *y = z->parent->parent->left;
if (y != NULL && y->color == 1) {
z->parent->color = ;
y->color = ;
z->parent->parent->color = 1;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotate(root, z);
}
z->parent->color = ;
z->parent->parent->color = 1;
left_rotate(root, z->parent->parent);
}
}
}
(*root)->color = ;
}
void insert(Node **root, int val) {
Node *node = create_node(val);
Node *y = NULL;
Node *x = *root;
while (x != NULL) {
y = x;
if (node->val < x->val) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y == NULL) {
*root = node;
} else if (node->val < y->val) {
y->left = node;
} else {
y->right = node;
}
insert_fixup(root, node);
}
void inorder(Node *node) {
if (node == NULL) {
return;
}
inorder(node->left);
printf("%d ", node->val);
inorder(node->right);
}
int main() {
Node *root = NULL;
insert(&root, 7);
insert(&root, 6);
insert(&root, 5);
insert(&root, 4);
insert(&root, 3);
insert(&root, 2);
insert(&root, 1);
inorder(root);
return ;
}
```
这是一个基本的红黑树实现,包括插入和左旋、右旋操作。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)