红黑树查找C语言代码,并保证红黑树的稳定性
时间: 2023-11-20 19:56:35 浏览: 62
红黑树求解C代码
以下是红黑树查找的C语言代码,同时保证了红黑树的稳定性:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义红黑树的颜色
#define RED 0
#define BLACK 1
// 定义红黑树的节点结构体
typedef struct rb_node {
int key; // 节点的键值
int color; // 节点的颜色
struct rb_node *left; // 左子节点
struct rb_node *right; // 右子节点
struct rb_node *parent; // 父节点
} rb_node;
// 定义红黑树的根节点
rb_node *root = NULL;
// 左旋函数
void left_rotate(rb_node *node) {
rb_node *right = node->right;
node->right = right->left;
if (right->left != NULL) {
right->left->parent = node;
}
right->parent = node->parent;
if (node->parent == NULL) {
root = right;
} else if (node == node->parent->left) {
node->parent->left = right;
} else {
node->parent->right = right;
}
right->left = node;
node->parent = right;
}
// 右旋函数
void right_rotate(rb_node *node) {
rb_node *left = node->left;
node->left = left->right;
if (left->right != NULL) {
left->right->parent = node;
}
left->parent = node->parent;
if (node->parent == NULL) {
root = left;
} else if (node == node->parent->right) {
node->parent->right = left;
} else {
node->parent->left = left;
}
left->right = node;
node->parent = left;
}
// 插入函数
void insert(int key) {
rb_node *node = (rb_node *)malloc(sizeof(rb_node));
node->key = key;
node->color = RED;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
rb_node *x = root;
rb_node *y = NULL;
while (x != NULL) {
y = x;
if (node->key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y == NULL) {
root = node;
} else if (node->key < y->key) {
y->left = node;
} else {
y->right = node;
}
while (node != root && node->parent->color == RED) {
if (node->parent == node->parent->parent->left) {
rb_node *uncle = node->parent->parent->right;
if (uncle != NULL && uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->right) {
node = node->parent;
left_rotate(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
right_rotate(node->parent->parent);
}
} else {
rb_node *uncle = node->parent->parent->left;
if (uncle != NULL && uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
right_rotate(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
left_rotate(node->parent->parent);
}
}
}
root->color = BLACK;
}
// 查找函数
rb_node *search(int key) {
rb_node *node = root;
while (node != NULL && node->key != key) {
if (key < node->key) {
node = node->left;
} else {
node = node->right;
}
}
return node;
}
// 中序遍历函数
void inorder(rb_node *node) {
if (node != NULL) {
inorder(node->left);
printf("%d ", node->key);
inorder(node->right);
}
}
int main() {
insert(10);
insert(20);
insert(30);
insert(40);
insert(50);
insert(60);
insert(70);
insert(80);
insert(90);
insert(100);
printf("中序遍历结果:");
inorder(root);
printf("\n");
rb_node *node = search(50);
if (node != NULL) {
printf("查找结果:key=%d, color=%d\n", node->key, node->color);
} else {
printf("查找结果:未找到\n");
}
return 0;
}
```
阅读全文