理解红黑树

lddfg · 2024 年5 月 29 日 09:32

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，具有以下性质：

节点是红色或黑色的。
根节点是黑色的。
所有叶子节点（NIL节点）都是黑色的。
每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些性质确保了红黑树的高度大致保持在 (O(\log_{2}n)) 的范围内，从而保证了基本操作（插入、删除、查找）的时间复杂度为 (O(\log n)) 。

红黑树的操作

红黑树的基本操作包括插入、删除和查找。由于红黑树是一种二叉搜索树，这些操作的实现与普通二叉搜索树类似，但在每次插入和删除操作后需要进行额外的调整以保持红黑树的性质。调整主要通过旋转和重新着色来实现。

插入操作

插入操作分为以下几个步骤：

常规的BST插入：将新节点插入到树中，按二叉搜索树的规则放置。
重新着色和旋转：通过重新着色和旋转来维护红黑树的性质。

删除操作

删除操作分为以下几个步骤：

常规的BST删除：找到待删除节点，并用其后继节点（如果存在）来替代。
重新着色和旋转：通过重新着色和旋转来维护红黑树的性质。

下面是一个红黑树的C实现示例：

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

typedef enum { RED, BLACK } Color;

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

typedef struct {
    Node *root;
    Node *NIL;  // Sentinel NIL node
} RBTree;

Node* new_node(int data, Color color, Node *left, Node *right, Node *parent) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->color = color;
    node->left = left;
    node->right = right;
    node->parent = parent;
    return node;
}

RBTree* create_rbtree() {
    RBTree *tree = (RBTree*)malloc(sizeof(RBTree));
    tree->NIL = new_node(0, BLACK, NULL, NULL, NULL); // Create the sentinel NIL node
    tree->root = tree->NIL;
    return tree;
}

void left_rotate(RBTree *tree, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left != tree->NIL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == tree->NIL) {
        tree->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(RBTree *tree, Node *y) {
    Node *x = y->left;
    y->left = x->right;
    if (x->right != tree->NIL) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == tree->NIL) {
        tree->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(RBTree *tree, Node *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node *y = z->parent->parent->right;
            if (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(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(tree, z->parent->parent);
            }
        } else {
            Node *y = z->parent->parent->left;
            if (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(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(tree, z->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

void rb_insert(RBTree *tree, int data) {
    Node *z = new_node(data, RED, tree->NIL, tree->NIL, tree->NIL);
    Node *y = tree->NIL;
    Node *x = tree->root;
    while (x != tree->NIL) {
        y = x;
        if (z->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == tree->NIL) {
        tree->root = z;
    } else if (z->data < y->data) {
        y->left = z;
    } else {
        y->right = z;
    }
    insert_fixup(tree, z);
}

void inorder_helper(Node *root, Node *NIL) {
    if (root != NIL) {
        inorder_helper(root->left, NIL);
        printf("%d ", root->data);
        inorder_helper(root->right, NIL);
    }
}

void inorder(RBTree *tree) {
    inorder_helper(tree->root, tree->NIL);
    printf("\n");
}

int main() {
    RBTree *tree = create_rbtree();
    rb_insert(tree, 10);
    rb_insert(tree, 20);
    rb_insert(tree, 30);
    rb_insert(tree, 15);
    rb_insert(tree, 25);
    rb_insert(tree, 5);

    printf("Inorder traversal: ");
    inorder(tree);

    return 0;
}

代码说明

数据结构定义：
- Node结构体包含了红黑树节点的所有必要信息。
- RBTree结构体包含了红黑树的根节点和一个NIL节点。
节点创建：
- new_node函数用于创建一个新的节点。
红黑树创建：
- create_rbtree函数用于创建一棵新的红黑树并初始化NIL节点。
旋转操作：
- left_rotate和right_rotate函数分别实现左旋转和右旋转。
插入修复：
- insert_fixup函数用于在插入新节点后维护红黑树的性质。
插入操作：
- rb_insert函数用于将新节点插入到红黑树中。
中序遍历：
- inorder_helper和inorder函数用于中序遍历红黑树并打印节点数据。

结论

红黑树是一种重要的自平衡二叉搜索树，能够保证在最坏情况下基本操作的时间复杂度为 (O(\log_{2}n)) 。