C语言实现手写红黑树的示例代码

前言

红黑树是一种自平衡的二叉查找树，它能够保持良好的高效性能和平衡性。在本问题中，我们将使用C语言来实现手写红黑树的示例代码。

实现代码

#include 
#include 

typedef struct Node {
  int data;
  struct Node *parent;
  struct Node *left;
  struct Node *right;
  int color;
} Node;

typedef struct RedBlackTree {
  Node *root;
  Node *nil;
} RedBlackTree;

// 函数声明
void insert(RedBlackTree *tree, int data);
void insertFixUp(RedBlackTree *tree, Node *newNode);
void leftRotate(RedBlackTree *tree, Node *node);
void rightRotate(RedBlackTree *tree, Node *node);

// 实现代码
void insert(RedBlackTree *tree, int data) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->data = data;
  newNode->left = tree->nil;
  newNode->right = tree->nil;
  newNode->color = 1;  // 默认插入红色节点

  Node *current = tree->root;
  Node *parent = tree->nil;

  while (current != tree->nil) {
    parent = current;
    if (data < current->data) {
      current = current->left;
    } else {
      current = current->right;
    }
  }

  newNode->parent = parent;
  if (parent == tree->nil) {
    tree->root = newNode;  // 插入根节点
  } else if (data < parent->data) {
    parent->left = newNode;  // 插入左子节点
  } else {
    parent->right = newNode;  // 插入右子节点
  }

  insertFixUp(tree, newNode);
}

void insertFixUp(RedBlackTree *tree, Node *newNode) {
  while (newNode->parent->color == 1) {
    if (newNode->parent == newNode->parent->parent->left) {
      Node *uncle = newNode->parent->parent->right;
      if (uncle->color == 1) {
        newNode->parent->color = 0;
        uncle->color = 0;
        newNode->parent->parent->color = 1;
        newNode = newNode->parent->parent;
      } else {
        if (newNode == newNode->parent->right) {
          newNode = newNode->parent;
          leftRotate(tree, newNode);
        }
        newNode->parent->color = 0;
        newNode->parent->parent->color = 1;
        rightRotate(tree, newNode->parent->parent);
      }
    } else {
      Node *uncle = newNode->parent->parent->left;
      if (uncle->color == 1) {
        newNode->parent->color = 0;
        uncle->color = 0;
        newNode->parent->parent->color = 1;
        newNode = newNode->parent->parent;
      } else {
        if (newNode == newNode->parent->left) {
          newNode = newNode->parent;
          rightRotate(tree, newNode);
        }
        newNode->parent->color = 0;
        newNode->parent->parent->color = 1;
        leftRotate(tree, newNode->parent->parent);
      }
    }
  }
  tree->root->color = 0;
}

void leftRotate(RedBlackTree *tree, Node *node) {
  Node *rightChild = node->right;
  node->right = rightChild->left;

  if (rightChild->left != tree->nil) {
    rightChild->left->parent = node;
  }

  rightChild->parent = node->parent;

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

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

void rightRotate(RedBlackTree *tree, Node *node) {
  Node *leftChild = node->left;
  node->left = leftChild->right;

  if (leftChild->right != tree->nil) {
    leftChild->right->parent = node;
  }

  leftChild->parent = node->parent;

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

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

代码解释

上述代码是一个简单的红黑树实现的示例代码。

首先，我们定义了Node结构体来表示树节点。Node结构体包含数据（data）、父节点指针（parent）、左子节点指针（left）、右子节点指针（right）和颜色标记（color）。其中，color为0表示节点颜色为黑色，为1表示节点颜色为红色。

接着，我们定义了RedBlackTree结构体来表示红黑树。该结构体包含一个指向根节点的指针（root）和一个指向哨兵节点的指针（nil）。哨兵节点用于表示树的叶子节点，颜色为黑色。哨兵节点的使用可以简化红黑树的实现过程。

在insert函数中，我们首先创建一个新节点newNode，并初始化相关成员。然后，我们使用类似二叉查找树的方式找到newNode应该插入的位置，并进行插入操作。插入过程中，还需要调用insertFixUp函数进行红黑树的调整，以确保插入的节点满足红黑树的性质。

insertFixUp函数是红黑树的调整过程，它根据新插入节点的父节点和叔节点的颜色进行不同的旋转操作，以保证红黑树的平衡性。

leftRotate和rightRotate函数分别实现了左旋和右旋的操作。这两个操作都是在保持红黑树的性质不变的前提下，通过旋转操作来改变树的结构。

总结

红黑树是一种非常有用的数据结构，它能够在插入和删除操作时自动保持树的平衡，从而提供较好的性能。本文展示了如何使用C语言实现手写红黑树的示例代码。代码中包含了插入节点、节点旋转和调整红黑树平衡的相关操作。希望通过本示例代码的解释，您能更好地理解和应用红黑树的概念和实现。