三、红黑树
红黑树讲解比较麻烦，以下的gpt对我实现的代码的总结
Red-Black Tree 通过如下的方式进行自平衡：
节点是红色或黑色。
根节点是黑色。
所有叶子节点（NIL节点，空节点）是黑色。
每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有路径包含相同数目黑色节点。
具体实现时，我们可以定义 Node 类来表示红黑树的节点，其中包括节点的键、值、颜色等属性。具体的实现需要考虑以下情况：
插入节点
在插入节点时，我们需要考虑节点的颜色和位置，以保证插入后仍然满足红黑树的性质。以下是插入节点的具体实现细节：
插入到空树
当插入到空树时，我们需要创建一个根节点，将其颜色设置为黑色，并将新节点插入作为根节点的左孩子或右孩子。
插入到非空树
首先通过二叉搜索树的插入方式找到新节点要插入的位置，然后将新节点插入到该位置，并将其颜色设置为红色。接下来需要保证红黑树的性质，具体实现如下：
如果新节点的父节点为黑色，则满足红黑树的性质，无需处理。
如果新节点的父节点为红色，则需要进行变色或旋转操作，以满足红黑树的性质。
为了方便后续实现，以下称新插入的节点为 X，X 的父节点为 P，X 的祖父节点为 G，X 的叔父节点为 U。具体的情况如下：
Case 1：如果 P 为根节点，则将其颜色设置为黑色。
Case 2：如果 P 的颜色为黑色，则满足红黑树的性质，无需处理。
Case 3：如果 P 和 U 都为红色，则将 P 和 U 的颜色都设置为黑色，G 的颜色设置为红色，然后将 X 的位置设置为 G，继续向上判断。
Case 4：如果 P 为红色，U 为黑色，并且 X 是 P 的右孩子而且 P 是 G 的左孩子，或者 X 是 P 的左孩子而且 P 是 G 的右孩子，则需要进行旋转操作。具体操作如下：
如果 X 是 P 的右孩子，将 X 和 P 交换，得到情况 "X 是 P 的左孩子，P 是 G 的左孩子"。
将 P 向左旋转，得到情况 "X 是 P 的左孩子，P 是 G 的左孩子，X 的兄弟节点为 P"。
将 P 和 G 的颜色互换，得到最终的结果。
Case 5：如果 P 为红色，U 为黑色，并且 X 是 P 的左孩子而且 P 是 G 的左孩子，或者 X 是 P 的右孩子而且 P 是 G 的右孩子，则需要进行旋转操作。具体操作如下：
将 P 和 G 的颜色互换，得到情况 "X 是 P 的右孩子，P 是 G 的右孩子"。
将 P 向右旋转，得到情况 "X 是 P 的右孩子，P 是 G 的右孩子，X 的兄弟节点为 P"。
将 P 和 G 的颜色互换，得到最终的结果。
删除节点
在删除节点时，我们需要考虑节点的颜色和位置，以保证删除后仍然满足红黑树的性质。以下是删除节点的具体实现细节：
删除叶子节点
直接删除该节点，并将其父节点指向 NULL。
删除有一个子节点的节点
将该节点的子节点接到其父节点上，并删除该节点。
删除有两个子节点的节点
在右子树中找到最小的节点，将其值和键复制到要删除的节点，然后删除右子树中的最小节点。
在删除节点时，如果节点的颜色为黑色，还需要进一步处理，以保证红黑树的性质。如果删除的节点是叶子节点或只有一个子节点的节点，删除时并不会破坏红黑树的性质。如果删除的节点有两个子节点，需要找到其后继节点（即右子树中的最小节点），然后用后继节点替换要删除的节点，此时后继节点的颜色可能是红色或黑色，需要进行进一步处理，具体实现如下：
Case 1：如果后继节点是红色，则将其颜色设置为黑色。
Case 2：如果后继节点是黑色，并且其任一子节点是红色，则将其子节点的颜色设置为黑色，并将后继节点的颜色设置为红色。
Case 3：如果后继节点是黑色，并且其子节点都是黑色，则需要进行变色或旋转操作，以满足红黑树的性质。
为了方便后续实现，以下称要删除的节点为 X，X 的父节点为 P，X 的兄弟节点为 S，S 的子节点为 S1 和 S2，S1 或 S2 和 S 的颜色为红色。具体的情况如下：
Case 1：如果 X 是根节点，则将其颜色设置为黑色。
Case 2：如果 X 的兄弟节点 S 是红色，则将 S 的颜色设置为黑色，P 的颜色设置为红色，然后对 P 进行旋转操作，使 X 的兄弟节点为黑色。
Case 3：如果 X、X 的父节点 P 和 X 的兄弟节点 S 都是黑色，并且 S 的子节点都是黑色，则将 S 的颜色设置为红色，将 X 的位置设置为 P，继续向上判断。
Case 4：如果 X 的兄弟节点 S 是黑色，S 的左孩子 S1 是红色，S 的右孩子 S2 是黑色，则进行以下操作：
将 S 和 S1 的颜色互换，得到情况 "X 的兄弟节点 S 的右孩子 S2 是红色"。
将 S 向右旋转，将 S2 和 P 的颜色也进行相应的变换，得到情况 "X 的兄弟节点 S 的左孩子 S1 是黑色，S 的右孩子 S2 是红色"。
重新设置 S、S1 和 S2 的颜色，得到最终的结果。
Case 5：如果 X 的兄弟节点 S 是黑色，S 的右孩子 S2 是红色，则进行以下操作：
将 S 和 S2 的颜色互换，得到情况 "X 的兄弟节点 S 的左孩子 S1 是黑色"。
将 S 向左旋转，将 S1 和 P 的颜色也进行相应的变换，得到情况 "X 的兄弟节点 S 的左孩子 S1 是红色，S 的右孩子 S2 是黑色"。
重新设置 S、S1 和 S2 的颜色，得到最终的结果。
Case 6：如果 X 的兄弟节点 S 是黑色，S 的左孩子 S1 是红色，则进行以下操作：
将 S 和 S1 的颜色互换，得到情况 "X 的兄弟节点 S 的右孩子 S2 是黑色"。
将 S 向右旋转，将 S2 和 P 的颜色也进行相应的变换，得到情况 "X 的兄弟节点 S 的左孩子 S1 是黑色，S 的右孩子 S2 是红色"。
重新设置 S、S1 和 S2 的颜色，得到最终的结果。
以上就是 Red-Black Tree 的实现细节和各种情况的判断，希望能对您有所帮助。
以下是代码及其一些细节
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; // 红黑树节点的颜色，红色表示节点为2节点（即2-3树中的3节点中的左子节点或者右子节点），黑色表示节点为3节点或空节点 enum Color { RED, BLACK }; // 红黑树节点的类 class RBNode { public: int key; // 节点的键 int value; // 节点的值 Color color; // 节点的颜色，红色或者黑色 RBNode* left; // 节点的左子节点，可以是红节点或者黑节点 RBNode* right; // 节点的右子节点，可以是红节点或者黑节点 // 构造函数 RBNode(int key, int value, Color color) : key(key), value(value), color(color), left(nullptr), right(nullptr) {} }; // 红黑树的类 class RBTree { private: RBNode* root; public: // 构造函数 RBTree() : root(nullptr) {} // 插入操作 void insert(int key, int value) { root = insert_node(root, key, value); // 调用私有的插入节点函数 root->color = BLACK; // 根节点必须为黑色 } // 查找操作 int search(int key) { RBNode* node = search_node(root, key); // 调用私有的查找节点函数 if (node != nullptr) { return node->value; } else { return -1; } } // 删除操作 void erase(int key) { root = erase_node(root, key); // 调用私有的删除节点函数 if (root != nullptr) { root->color = BLACK; // 根节点必须为黑色 } } // 查询最大键值 int max() { RBNode* node = max_node(root); if (node != nullptr) { return node->key; } else { return -1; } } // 查询最小键值 int min() { RBNode* node = min_node(root); if (node != nullptr) { return node->key; } else { return -1; } } private: // 左旋操作 RBNode* left_rotate(RBNode* node) { RBNode* right_child = node->right; // 获取需要左旋的节点的右子节点 node->right = right_child->left; // 右子节点的左子节点变成需要左旋的节点的右子节点 right_child->left = node; // 需要左旋的节点变成右子节点的左子节点 right_child->color = node->color; // 右子节点颜色变成需要左旋的节点的颜色 node->color = RED; // 需要左旋的节点变成红色 return right_child; // 返回左旋后的根节点 } // 右旋操作 RBNode* right_rotate(RBNode* node) { RBNode* left_child = node->left; // 获取需要右旋的节点的左子节点 node->left = left_child->right; // 左子节点的右子节点变成需要右旋的节点的左子节点 left_child->right = node; // 需要右旋的节点变成左子节点的右子节点 left_child->color = node->color; // 左子节点颜色变成需要右旋的节点的颜色 node->color = RED; // 需要右旋的节点变成红色 return left_child; // 返回右旋后的根节点 } // 颜色翻转操作 void flip_color(RBNode* node) { node->color = RED; // 需要翻转颜色的节点变成红色 node->left->color = BLACK; // 左子节点和右子节点变成黑色 node->right->color = BLACK; } // 插入节点 RBNode* insert_node(RBNode* node, int key, int value) { if (node == nullptr) { return new RBNode(key, value, RED); // 如果节点是空节点，则创建一个红色节点 } if (key < node->key) { node->left = insert_node(node->left, key, value); // 插入到左子树 } else if (key > node->key) { node->right = insert_node(node->right, key, value); // 插入到右子树 } else { node->value = value; // 如果节点已经存在，则更新节点的值 } // 实施红黑树的正常插入操作 if (is_red(node->right) && !is_red(node->left)) { // 如果需要右旋 node = left_rotate(node); } if (is_red(node->left) && is_red(node->left->left)) { // 如果需要左旋 node = right_rotate(node); } if (is_red(node->left) && is_red(node->right)) { // 如果需要颜色翻转 flip_color(node); } return node; } // 删除节点 RBNode* erase_node(RBNode* node, int key) { if (node == nullptr) { return nullptr; } if (key < node->key) { node->left = erase_node(node->left, key); // 删除左子树的节点 } else if (key > node->key) { node->right = erase_node(node->right, key); // 删除右子树的节点 } else { if (node->left == nullptr) { RBNode* right_child = node->right; delete node; return right_child; } if (node->right == nullptr) { RBNode* left_child = node->left; delete node; return left_child; } RBNode* replace_node = min_node(node->right); // 找到右子树中的最小节点 node->key = replace_node->key; // 用最小节点替换需要删除的节点 node->value = replace_node->value; node->right = erase_min(node->right); // 删除替换节点，即删除右子树中的最小节点 } // 实施红黑树的删除后的修正操作 if (is_red(node->right) && !is_red(node->left)) { // 如果需要右旋和颜色翻转 node = left_rotate(node); } if (is_red(node->left) && is_red(node->left->left)) { // 如果需要左旋和颜色翻转 node = right_rotate(node); } if (is_red(node->left) && is_red(node->right)) { // 如果需要颜色翻转 flip_color(node); } return node; } // 删除最小键值节点 RBNode* erase_min(RBNode* node) { if (node->left == nullptr) { RBNode* right_child = node->right; delete node; return right_child; } if (!is_red(node->left) && !is_red(node->left->left)) { // 如果左子节点为黑色且左子节点的左子节点为黑色，则进行颜色翻转 node = move_red_left(node); } node->left = erase_min(node->left); // 递归删除左子树的最小键值节点 return balance(node); // 做一次平衡操作 } // 将左子树的红节点移到右子树中 RBNode* move_red_left(RBNode* node) { flip_color(node); // 颜色翻转 if (is_red(node->right->left)) { // 如果右子节点的左子节点为红色，则右旋 node->right = right_rotate(node->right); node = left_rotate(node); flip_color(node); } return node; } // 查询节点 RBNode* search_node(RBNode* node, int key) { if (node == nullptr) { return nullptr; // 节点不存在，则返回空指针 } if (key < node->key) { return search_node(node->left, key); // 继续在左子树中查找 } else if (key > node->key) { return search_node(node->right, key);// 继续在右子树中查找 } else { return node; // 找到节点，则返回指向该节点的指针 } } // 查询最大节点 RBNode* max_node(RBNode* node) { if (node->right == nullptr) { // 如果节点的右子树为空，则该节点为最大节点 return node; } else { return max_node(node->right); // 继续在右子树中查找 } } // 查询最小节点 RBNode* min_node(RBNode* node) { if (node->left == nullptr) { // 如果节点的左子树为空，则该节点为最小节点 return node; } else { return min_node(node->left); // 继续在左子树中查找 } } // 平衡操作，保证每个节点左右子树中黑节点的数量相等 RBNode* balance(RBNode* node) { if (is_red(node->right)) { // 如果右子节点为红色，则左旋 node = left_rotate(node); } if (is_red(node->left) && is_red(node->left->left)) { // 如果左子节点为红色且左子节点的左子节点为红色，则右旋 node = right_rotate(node); } if (is_red(node->left) && is_red(node->right)) { // 如果左右子节点都为红色，则进行颜色翻转 flip_color(node); } return node; // 返回平衡后的根节点 } // 判断节点的颜色是否为红色，如果节点为nullptr，则其颜色为黑色 bool is_red(RBNode* node) { return (node != nullptr && node->color == RED); } }; int main() { RBTree tree; tree.insert(3, 5); // 插入键值为3，值为5的节点 tree.insert(1, 10); // 插入键值为1，值为10的节点 tree.insert(5, 7); // 插入键值为5，值为7的节点 cout << tree.search(3) << endl; // 查询键值为3的节点的值，输出5 cout << tree.search(2) << endl; // 查询键值为2的节点的值，输出-1，表示未找到 cout << tree.max() << endl; // 查询红黑树中最大的键的值，输出5 cout << tree.min() << endl; // 查询红黑树中最小的键的值 }
