c语言写一个红黑树代码
时间: 2023-08-02 13:45:01 浏览: 95
红黑树C语言代码
以下是一个简单的红黑树实现,包括插入节点、查找节点和删除节点的基本操作:
```
#include <stdio.h>
#include <stdlib.h>
enum Color {RED, BLACK};
typedef struct Node {
int key;
enum Color color;
struct Node *left, *right, *parent;
} Node;
Node *root = NULL;
void rotate_left(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 rotate_right(Node *x) {
Node *y = x->left;
x->left = y->right;
if (y->right != NULL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
root = y;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void insert_fixup(Node *z) {
while (z->parent != NULL && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node *y = z->parent->parent->right;
if (y != NULL && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else {
if (z == z->parent->right) {
z = z->parent;
rotate_left(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotate_right(z->parent->parent);
}
}
else {
Node *y = z->parent->parent->left;
if (y != NULL && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else {
if (z == z->parent->left) {
z = z->parent;
rotate_right(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotate_left(z->parent->parent);
}
}
}
root->color = BLACK;
}
void insert(int key) {
Node *z = malloc(sizeof(Node));
z->key = key;
z->color = RED;
z->left = NULL;
z->right = NULL;
z->parent = NULL;
Node *y = NULL;
Node *x = root;
while (x != NULL) {
y = x;
if (key < x->key) {
x = x->left;
}
else {
x = x->right;
}
}
z->parent = y;
if (y == NULL) {
root = z;
}
else if (key < y->key) {
y->left = z;
}
else {
y->right = z;
}
insert_fixup(z);
}
Node *tree_minimum(Node *x) {
while (x->left != NULL) {
x = x->left;
}
return x;
}
void transplant(Node *u, Node *v) {
if (u->parent == NULL) {
root = v;
}
else if (u == u->parent->left) {
u->parent->left = v;
}
else {
u->parent->right = v;
}
if (v != NULL) {
v->parent = u->parent;
}
}
void delete_fixup(Node *x) {
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotate_left(x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
}
else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotate_right(w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotate_left(x->parent);
x = root;
}
}
else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotate_right(x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
}
else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotate_left(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotate_right(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
void delete(int key) {
Node *z = root;
while (z != NULL) {
if (key == z->key) {
break;
}
else if (key < z->key) {
z = z->left;
}
else {
z = z->right;
}
}
if (z == NULL) {
return;
}
Node *y = z;
enum Color y_original_color = y->color;
if (z->left == NULL) {
Node *x = z->right;
transplant(z, z->right);
free(z);
if (x != NULL) {
delete_fixup(x);
}
}
else if (z->right == NULL) {
Node *x = z->left;
transplant(z, z->left);
free(z);
if (x != NULL) {
delete_fixup(x);
}
}
else {
y = tree_minimum(z->right);
y_original_color = y->color;
Node *x = y->right;
if (y->parent == z) {
if (x != NULL) {
x->parent = y;
}
}
else {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
free(z);
if (x != NULL) {
delete_fixup(x);
}
}
}
void inorder_traversal(Node *x) {
if (x != NULL) {
inorder_traversal(x->left);
printf("%d ", x->key);
inorder_traversal(x->right);
}
}
Node *search(int key) {
Node *x = root;
while (x != NULL) {
if (key == x->key) {
return x;
}
else if (key < x->key) {
x = x->left;
}
else {
x = x->right;
}
}
return NULL;
}
int main() {
insert(10);
insert(20);
insert(30);
insert(15);
insert(18);
insert(25);
insert(40);
inorder_traversal(root);
printf("\n");
delete(20);
inorder_traversal(root);
printf("\n");
Node *x = search(15);
if (x != NULL) {
printf("%d\n", x->key);
}
return 0;
}
```
注:此红黑树实现没有考虑内存泄漏的情况。
阅读全文