用c语言实现红黑二叉树
时间: 2023-10-23 20:11:53 浏览: 49
红黑树是一种自平衡二叉查找树,它保证了在最坏情况下基本动态操作的时间复杂度为 O(logn)。下面是使用c语言实现红黑树的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED, BLACK } Color;
typedef struct node {
int key;
Color color;
struct node* left;
struct node* right;
struct node* parent;
} Node;
Node* create_node(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->color = RED;
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 == 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;
left_rotate(root, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(root, 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;
right_rotate(root, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(root, z->parent->parent);
}
}
}
(*root)->color = BLACK;
}
void insert(Node** root, int key) {
Node* z = create_node(key);
Node* y = NULL;
Node* x = *root;
while (x != NULL) {
y = x;
if (z->key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == NULL) {
*root = z;
} else if (z->key < y->key) {
y->left = z;
} else {
y->right = z;
}
insert_fixup(root, z);
}
void inorder_traversal(Node* node) {
if (node != NULL) {
inorder_traversal(node->left);
printf("%d ", node->key);
inorder_traversal(node->right);
}
}
int main() {
Node* root = NULL;
insert(&root, 10);
insert(&root, 20);
insert(&root, 30);
insert(&root, 15);
insert(&root, 18);
insert(&root, 25);
insert(&root, 40);
printf("Inorder Traversal: ");
inorder_traversal(root);
printf("\n");
return 0;
}
```
在这个示例代码中,我们使用了如下的红黑树操作:
- `create_node`: 创建一个新的节点。
- `left_rotate`: 左旋操作,将一个节点向左旋转。
- `right_rotate`: 右旋操作,将一个节点向右旋转。
- `insert_fixup`: 插入一个节点后修复红黑树的性质。
- `insert`: 插入一个新的节点。
- `inorder_traversal`: 中序遍历红黑树。
在主函数中,我们使用 `insert` 操作插入了一些节点,然后使用 `inorder_traversal` 操作中序遍历红黑树,并打印出结果。