写一个 C 语言版的 红黑树

我可以给你一个简单的C语言版本的红黑树：#include<stdio.h>struct Node
{
int data;
enum {RED, BLACK} color;
struct Node *left, *right, *parent;
};struct Node* root;void insert(int data)
{
struct Node *z = (struct Node*)malloc(sizeof(struct Node));
z->data = data;
z->left = NULL;
z->right = NULL;
z->color = RED;

struct Node *y = NULL;
struct Node *x = root;

while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == NULL)
root = z;
else if (z->data < y->data)
y->left = z;
else
y->right = z;
}

相关问题

使用C++写一颗红黑树

### 回答1：
好的，这是一个使用 C 语言写的红黑树的示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct rbtree_node_t {
  int key;
  char color;
  struct rbtree_node_t *left;
  struct rbtree_node_t *right;
  struct rbtree_node_t *parent;
} rbtree_node;

typedef struct rbtree_t {
  rbtree_node *root;
} rbtree;

rbtree_node *rbtree_node_create(int key) {
  rbtree_node *node = malloc(sizeof(rbtree_node));
  node->key = key;
  node->color = 'R';
  node->left = NULL;
  node->right = NULL;
  node->parent = NULL;
  return node;
}

void rbtree_left_rotate(rbtree *tree, rbtree_node *node) {
  rbtree_node *right_child = node->right;
  node->right = right_child->left;

  if (right_child->left != NULL) {
    right_child->left->parent = node;
  }

  right_child->parent = node->parent;

  if (node->parent == NULL) {
    tree->root = right_child;
  } else if (node == node->parent->left) {
    node->parent->left = right_child;
  } else {
    node->parent->right = right_child;
  }

  right_child->left = node;
  node->parent = right_child;
}

void rbtree_right_rotate(rbtree *tree, rbtree_node *node) {
  rbtree_node *left_child = node->left;
  node->left = left_child->right;

  if (left_child->right != NULL) {
    left_child->right->parent = node;
  }

  left_child->parent = node->parent;

  if (node->parent == NULL) {
    tree->root = left_child;
  } else if (node == node->parent->right) {
    node->parent->right = left_child;
  } else {
    node->parent->left = left_child;
  }

  left_child->right = node;
  node->parent = left_child;
}

void rbtree_insert_fixup(rbtree *tree, rbtree_node *node) {
  while (node != tree->root && node->parent->color == 'R') {
    if (node->parent == node->parent->parent->left) {
      rbtree_node *uncle = node->parent->parent->right;
      if (uncle != NULL && uncle->color == 'R') {
        node->parent->color = 'B';
        uncle->color = 'B';
        node->parent->parent->color = 'R';
        node = node->parent->  

### 回答2：
红黑树是一种自平衡的二叉查找树，其中的节点被标记为红色或黑色。红黑树的目的是确保在进行插入和删除操作后，树保持近似平衡，并且具有良好的搜索性能。

在C语言中，可以通过定义结构体表示红黑树的节点，每个节点包含键值、颜色标记以及左右子节点的指针。以下是一个简化版的红黑树实现：

#include <stdio.h>
#include <stdlib.h>

typedef enum {RED, BLACK} Color;

typedef struct Node {
int key;
Color color;
struct Node *left, *right, *parent;
} Node;

Node *root = NULL;

void insert(int key) {
Node *z = (Node*)malloc(sizeof(Node));
z->key = key;
z->color = RED;
z->left = z->right = 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;

// 修正红黑树
while (z != root && 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 {
// 对称操作
}
}
root->color = BLACK;
}

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) {
// 对称操作
}

int main() {
int keys[] = {5, 3, 7, 1, 4, 6, 9};
int n = sizeof(keys) / sizeof(keys[0]);

for (int i = 0; i < n; i++)
insert(keys[i]);

// 在这里进行红黑树的使用

return 0;
}

这个简化的红黑树实现包括了插入操作和左旋操作，右旋操作与左旋操作对称。在主函数中，我们可以调用`insert`函数将一系列键值插入红黑树中，然后在注释的位置使用红黑树的功能。

红黑树的使用方法和二叉查找树相似，但由于自平衡的特性，红黑树在插入和删除操作后能够保持近似平衡，从而具有更好的性能和更短的搜索路径。  

### 回答3：
红黑树是一种自平衡的二叉搜索树，它在每次插入或删除操作后会通过旋转和重新着色来保持树的平衡性，从而保证了在最坏情况下的搜索性能。

使用C语言来实现红黑树，我们需要首先定义一个结构体来表示树的每个节点，包括节点的值、颜色以及左右子节点等信息。

然后可以实现一些基本的操作函数，如插入节点、删除节点以及搜索等。在这些函数中需要根据红黑树的特性来进行相关的旋转和重着色操作。

在实现插入函数时，可以通过先按照二叉搜索树的规则将节点插入到适当的位置，然后再通过旋转和重新着色来保持红黑树的平衡。

在实现删除函数时，需要首先找到要删除的节点，并根据它的子节点情况进行相应的操作，以保证删除后的树仍然是一颗红黑树。

在搜索函数中，可以利用红黑树的特性，在树中进行二分查找来提高搜索的效率。

除了基本的操作函数，还可以实现一些辅助函数来进行树的遍历、打印以及销毁等操作。

总之，使用C语言可以很好地实现一颗红黑树。通过合理的数据结构和算法设计，我们可以保证树的平衡性和搜索性能。

平衡树和红黑树的书籍

有几本关于平衡树和红黑树的书籍可以推荐给你：

1. 《算法导论》（Introduction to Algorithms）- Thomas H. Cormen 等人
这本经典教材详细介绍了平衡树和红黑树的原理、性质和实现，并提供了相应的伪代码和示例。

2. 《数据结构与算法分析》（Data Structures and Algorithm Analysis in C++）- Mark Allen Weiss
该书深入讲解了平衡树和红黑树的概念、应用和实现方法，并提供了C++代码示例。

3. 《算法（第4版）》（Algorithms, Part I）- Robert Sedgewick, Kevin Wayne
这本书由知名算法专家撰写，其中包含了对平衡树和红黑树的讲解，配有Java代码示例。

4. 《数据结构与算法分析：C语言描述》（Data Structures and Algorithm Analysis in C）- Clifford A. Shaffer
该书以C语言为基础，详细介绍了平衡树和红黑树的实现原理和应用，适合C语言开发者阅读。

以上是一些被广泛推荐的书籍，它们对于理解平衡树和红黑树的概念和实现方法非常有帮助。你可以根据自己的编程语言和阅读习惯选择适合的一本进行深入学习。