【数据结构】红黑树

红黑树

红黑树（Red-Black Tree）是一种自平衡二叉搜索树。它通过着色节点（红色或黑色）并确保遵循特定规则来保持树的平衡。这种结构的优点是查找、插入和删除操作都能够在平均情况下达到对数时间复杂度（O(log n)）。

红黑树的特性

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 所有叶节点（NULL）是黑色。
• 如果一个节点是红色的，那么它的两个子节点都是黑色的（即不存在红色节点连在一起的情况）。
• 从任一节点到其每个叶节点的路径都包含相同数量的黑色节点。

红黑树的操作

红黑树提供了基本的操作，包括插入、删除和查找操作。下面是这些操作的C语言实现。

定义节点结构

首先，我们定义红黑树的节点结构。除了包含一个整数值 value，指向左子树和右子树的指针 left 和 right 之外，我们还需要一个表示节点颜色的字段 color（红色或黑色）。

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int value;
    Color color;
    struct RBNode *left;
    struct RBNode *right;
    struct RBNode *parent;
} RBNode;

左旋和右旋操作

红黑树使用左旋和右旋操作来调整树的结构，确保树的平衡。

// 左旋操作
void leftRotate(RBNode **root, RBNode *x) {
    RBNode *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 rightRotate(RBNode **root, RBNode *y) {
    RBNode *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->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

左旋操作将节点 x 向左旋转，右旋操作将节点 y 向右旋转。这些操作用于调整树的结构。

插入操作

插入操作在红黑树中插入一个新的值，同时确保树保持平衡。插入后，需要调整节点的颜色和结构以维持红黑树的性质。

void insertFixup(RBNode **root, RBNode *z) {
    while (z->parent && z->parent->color == RED) {
        RBNode *parent = z->parent;
        RBNode *grandparent = parent->parent;
        if (parent == grandparent->left) {
            RBNode *uncle = grandparent->right;
            if (uncle && uncle->color == RED) {
                // 情况1：叔叔是红色的
                parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                z = grandparent;
            } else {
                if (z == parent->right) {
                    // 情况2：叔叔是黑色的，且当前节点是右子节点
                    z = parent;
                    leftRotate(root, z);
                    parent = z->parent;
                    grandparent = parent->parent;
                }
                // 情况3：叔叔是黑色的，且当前节点是左子节点
                parent->color = BLACK;
                grandparent->color = RED;
                rightRotate(root, grandparent);
            }
        } else {
            // 父节点是祖父节点的右子节点
            RBNode *uncle = grandparent->left;
            if (uncle && uncle->color == RED) {
                // 情况1：叔叔是红色的
                parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                z = grandparent;
            } else {
                if (z == parent->left) {
                    // 情况2：叔叔是黑色的，且当前节点是左子节点
                    z = parent;
                    rightRotate(root, z);
                    parent = z->parent;
                    grandparent = parent->parent;
                }
                // 情况3：叔叔是黑色的，且当前节点是右子节点
                parent->color = BLACK;
                grandparent->color = RED;
                leftRotate(root, grandparent);
            }
        }
    }
    // 确保根节点是黑色的
    (*root)->color = BLACK;
}

void insert(RBNode **root, int value) {
    RBNode *z = (RBNode*)malloc(sizeof(RBNode));
    z->value = value;
    z->color = RED; // 新插入的节点默认为红色
    z->left = z->right = z->parent = NULL;

    // 在树中找到插入位置
    RBNode *y = NULL;
    RBNode *x = *root;
    while (x != NULL) {
        y = x;
        if (value < x->value) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == NULL) {
        *root = z; // 新节点成为根节点
    } else if (value < y->value) {
        y->left = z;
    } else {
        y->right = z;
    }

    // 调整插入后的树结构
    insertFixup(root, z);
}

在插入操作中，我们首先找到插入位置，并将新插入的节点默认设置为红色。然后，通过 insertFixup 函数调整树的结构和颜色以确保红黑树的性质。

查找操作

查找操作在红黑树中查找特定值。查找过程与二叉搜索树类似，但红黑树可以在操作后确保树的平衡。

RBNode* search(RBNode* node, int value) {
    if (node == NULL || node->value == value) {
        return node;
    }

    // 根据值的大小决定查找方向
    if (value < node->value) {
        return search(node->left, value);
    } else {
        return search(node->right, value);
    }
}

查找操作递归地遍历树，根据值的大小选择左子树或右子树进行查找。

删除操作

删除操作在红黑树中删除特定值，同时确保树保持平衡。删除操作需要考虑多种情况，并可能触发旋转和调整操作。

// 右子树最小值
RBNode* minimum(RBNode* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除后修复红黑树的性质
void deleteFixup(RBNode **root, RBNode *x) {
    while (x != *root && x->color == BLACK) {
        if (x == x->parent->left) {
            RBNode *w = x->parent->right;
            if (w->color == RED) {
                // 情况1：兄弟是红色的
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(root, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                // 情况2：兄弟是黑色的，且兄弟的子节点也是黑色的
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    // 情况3：兄弟是黑色的，且兄弟的右子节点是黑色的
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(root, w);
                    w = x->parent->right;
                }
                // 情况4：兄弟是黑色的，且兄弟的右子节点是红色的
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(root, x->parent);
                x = *root;
            }
        } else {
            // 处理右子树的情况
            RBNode *w = x->parent->left;
            if (w->

color == RED) {
                // 情况1：兄弟是红色的
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(root, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                // 情况2：兄弟是黑色的，且兄弟的子节点也是黑色的
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    // 情况3：兄弟是黑色的，且兄弟的左子节点是黑色的
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(root, w);
                    w = x->parent->left;
                }
                // 情况4：兄弟是黑色的，且兄弟的左子节点是红色的
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(root, x->parent);
                x = *root;
            }
        }
    }
    x->color = BLACK;
}

RBNode* deleteNode(RBNode **root, RBNode *z) {
    RBNode *y = z;
    RBNode *x;
    Color originalColor = y->color;

    if (z->left == NULL) {
        x = z->right;
        if (x) {
            x->parent = y->parent;
        }
        if (z->parent == NULL) {
            *root = x;
        } else if (z == z->parent->left) {
            z->parent->left = x;
        } else {
            z->parent->right = x;
        }
    } else if (z->right == NULL) {
        x = z->left;
        if (x) {
            x->parent = y->parent;
        }
        if (z->parent == NULL) {
            *root = x;
        } else if (z == z->parent->left) {
            z->parent->left = x;
        } else {
            z->parent->right = x;
        }
    } else {
        y = minimum(z->right);
        originalColor = y->color;
        x = y->right;
        if (y->parent == z) {
            if (x) {
                x->parent = y;
            }
        } else {
            if (y->parent) {
                y->parent->left = x;
            }
            y->right = z->right;
            if (y->right) {
                y->right->parent = y;
            }
        }
        if (z->parent) {
            if (z == z->parent->left) {
                z->parent->left = y;
            } else {
                z->parent->right = y;
            }
        } else {
            *root = y;
        }
        y->parent = z->parent;
        y->color = z->color;
        y->left = z->left;
        if (y->left) {
            y->left->parent = y;
        }
    }

    if (originalColor == BLACK) {
        deleteFixup(root, x);
    }

    free(z);

    return x;
}

删除操作首先查找要删除的节点，然后根据节点的子节点情况处理。如果节点有两个子节点，需要找到右子树的最小值节点替换当前节点的值，然后递归删除右子树中的最小值节点。

总结

红黑树是一种自平衡二叉搜索树，通过着色节点并确保遵循特定规则来保持树的平衡。它提供了查找、插入和删除操作的对数时间复杂度，非常适合需要快速操作和高性能的数据结构。