类库与数据结构——红黑树

首先我们需要声明一下红黑树的概念。

红黑树（Red-Black Tree） 是一种自平衡的二叉搜索树，用于在保持数据有序的同时实现高效的数据插入、删除和查找操作。它广泛应用于关联容器（如C++ STL中的map和set）的底层实现中，以提供近似O(log n)的操作效率。

红黑树的特性

红黑树通过一组规则来维持树的平衡性，使得树的最长路径不会超过最短路径的两倍，从而避免退化为链表。红黑树的每个节点具有“红”或“黑”两种颜色，并满足以下特性：

节点颜色：每个节点不是红色就是黑色。
根节点为黑色：树的根节点始终为黑色。
叶子节点为黑色：所有空的叶子节点（NIL节点或NULL节点）都为黑色。
红色节点限制：红色节点的子节点必须为黑色（即，红色节点不能有两个红色子节点）。这意味着红色节点的父节点和子节点不能同时为红色，从而避免了长路径的形成。
从任一节点到其叶子节点的黑色节点路径一致：从任一节点到其每个叶子节点经过的黑色节点数量相同（称为“黑色高度”）。这种特性确保了树的平衡性。

红黑树的实现较为复杂，主要是因为需要通过颜色和旋转调整来保持树的平衡。

下面是红黑树的插入操作和调整的简化代码示例。由于红黑树的完整实现较长，我将提供插入节点的基本流程，并包含必要的旋转和颜色调整逻辑。

红黑树的节点定义和辅助操作

定义红黑树节点

每个节点包含一个color属性，用于表示节点的颜色（红色或黑色）。
颜色通常用布尔类型表示：true代表红色，false代表黑色。

enum Color {RED, BLACK};

struct TreeNode {
    int val;
    Color color;
    TreeNode *left, *right, *parent;

    TreeNode(int value) : val(value), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

左旋操作

左旋用于平衡树的结构，将当前节点的右孩子提升到父节点的位置。

TreeNode* leftRotate(TreeNode* root, TreeNode* node) {
    TreeNode* rightChild = node->right;
    node->right = rightChild->left;

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

    rightChild->parent = node->parent;

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

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

    return root;
}

右旋操作

右旋的原理与左旋类似，将当前节点的左孩子提升到父节点的位置。

TreeNode* rightRotate(TreeNode* root, TreeNode* node) {
    TreeNode* leftChild = node->left;
    node->left = leftChild->right;

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

    leftChild->parent = node->parent;

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

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

    return root;
}

红黑树插入操作和修复

红黑树的插入操作包括两个部分：插入节点 和 调整树，以保持红黑树的性质。

插入节点

插入节点时，默认将新节点设置为红色，并将其插入到适当的位置。
插入后需要调用修复函数来调整红黑树的结构。

TreeNode* insertNode(TreeNode* root, TreeNode* node) {
    // 二叉搜索树的插入过程
    if (root == nullptr) return node;

    if (node->val < root->val) {
        root->left = insertNode(root->left, node);
        root->left->parent = root;
    } else if (node->val > root->val) {
        root->right = insertNode(root->right, node);
        root->right->parent = root;
    }

    return root;
}

调整树的颜色和旋转

如果新插入节点的父节点是红色，则需要进行调整，以确保红黑树的性质。
调整包括以下几种情况：
- Case 1: 插入节点的父节点是黑色，不需要调整。
- Case 2: 插入节点的父节点是红色，且叔叔节点也是红色（父节点和叔叔节点都变黑，祖父节点变红）。
- Case 3: 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是右孩子（左旋）。
- Case 4: 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是左孩子（右旋）。
定义:对于一个节点 X 来说,叔叔节点是指 X 的父节点的兄弟节点（同一个祖父节点下的另一个子节点）。

TreeNode* fixInsert(TreeNode* root, TreeNode* node) {
    TreeNode *parent = nullptr;
    TreeNode *grandparent = nullptr;

    while ((node != root) && (node->color != BLACK) && (node->parent->color == RED)) {
        parent = node->parent;
        grandparent = node->parent->parent;

        // 父节点是祖父节点的左子节点
        if (parent == grandparent->left) {
            TreeNode* uncle = grandparent->right;

            // Case 1: 叔叔是红色 - 改变颜色
            if (uncle != nullptr && uncle->color == RED) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandparent;
            } else {
                // Case 2: 叔叔是黑色，且节点是右子节点 - 左旋
                if (node == parent->right) {
                    node = parent;
                    root = leftRotate(root, node);
                }

                // Case 3: 叔叔是黑色，且节点是左子节点 - 右旋
                parent->color = BLACK;
                grandparent->color = RED;
                root = rightRotate(root, grandparent);
            }
        }
        // 父节点是祖父节点的右子节点
        else {
            TreeNode* uncle = grandparent->left;

            // Case 1: 叔叔是红色 - 改变颜色
            if ((uncle != nullptr) && (uncle->color == RED)) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandparent;
            } else {
                // Case 2: 叔叔是黑色，且节点是左子节点 - 右旋
                if (node == parent->left) {
                    node = parent;
                    root = rightRotate(root, node);
                }

                // Case 3: 叔叔是黑色，且节点是右子节点 - 左旋
                parent->color = BLACK;
                grandparent->color = RED;
                root = leftRotate(root, grandparent);
            }
        }
    }
    root->color = BLACK;
    return root;
}

插入并修复树

插入节点后调用fixInsert函数进行调整，最终返回新的根节点。

TreeNode* insertAndFix(TreeNode* root, int value) {
    TreeNode* node = new TreeNode(value);
    root = insertNode(root, node);
    root = fixInsert(root, node);
    return root;
}

总结

红黑树的插入操作涉及多个步骤：

使用二叉搜索树的插入方式，将新节点插入到树中。
如果插入后违反红黑树的性质，调用fixInsert函数调整树的颜色和结构。
通过颜色变化和旋转操作，使树重新满足红黑树的性质。