红黑树概念

**红黑树概念**

红黑树是一种自平衡二叉查找树，用于实现快速的数据存储和检索。它通过在每个节点上维护一个颜色（红或黑）来保持平衡，从而保证了对树的操作（插入、删除等）的时间复杂度。

**基本概念**

红黑树有以下几个关键特征：

1. **每个节点都有一个颜色**：红黑树中的每个节点都被标记为红色或黑色。
2. **根节点是黑色的**：红黑树的根节点始终是黑色的。
3. **叶子节点（空节点）是黑色的**：叶子节点（即没有孩子的节点）都是黑色的。
4. **如果一个节点是红色的，则它的儿女都必须是黑色的**：这意味着，任何一个红色节点的孩子都是黑色的。
5. **对于任意一个节点，如果从该节点到其叶子节点之间的路径上有黑色颜色个数相同，则该节点是平衡的**：这保证了树在任何情况下都保持平衡。

**插入操作**

当我们需要向红黑树中插入一个新元素时，我们首先将其作为一个新的红色叶子节点添加到树中。然后，我们通过一系列旋转和颜色的改变来维持树的平衡性。

1. **插入新元素**：首先，将新元素作为一个新的红色叶子节点添加到树中。
2. **检查是否需要旋转**：如果新元素的父节点是黑色的，则不需要进行任何操作。如果新元素的父节点是红色的，则需要进行旋转和颜色的改变来维持平衡性。

**删除操作**

当我们需要从红黑树中删除一个元素时，我们首先找到该元素，然后将其替换为它的后继者（即它的右孩子）。然后，我们通过一系列旋转和颜色的改变来维持树的平衡性。

1. **找到要删除的元素**：首先，找到需要被删除的元素。
2. **将其替换为后继者**：将该元素替换为它的后继者（即它的右孩子）。
3. **检查是否需要旋转**：如果被删除的元素是红色的，则不需要进行任何操作。如果被删除的元素是黑色的，则需要进行旋转和颜色的改变来维持平衡性。

**示例代码**

下面是一个简单的红黑树实现的示例代码：

cpp#include <iostream>
using namespace std;

// 红黑树节点结构体struct Node {
 int key;
 char color; // 节点颜色（红或黑）
 Node* left;
 Node* right;
};

// 红黑树类class RedBlackTree {
public:
 Node* root; // 根节点 // 构造函数 RedBlackTree() : root(nullptr) {}

 // 销毁函数 ~RedBlackTree() { destroy(root); }

 // 插入新元素 void insert(int key) {
 Node* newNode = new Node();
 newNode->key = key;
 newNode->color = 'R'; // 新节点为红色 newNode->left = newNode->right = nullptr;

 if (root == nullptr) {
 root = newNode;
 } else {
 insertNode(root, newNode);
 }
 }

 // 删除元素 void remove(int key) {
 Node* nodeToRemove = findNode(root, key);

 if (nodeToRemove != nullptr) {
 destroy(nodeToRemove);
 }
 }

private:
 // 查找节点 Node* findNode(Node* currentNode, int key) {
 if (currentNode == nullptr || currentNode->key == key) {
 return currentNode;
 } else if (key < currentNode->key) {
 return findNode(currentNode->left, key);
 } else {
 return findNode(currentNode->right, key);
 }
 }

 // 插入新节点 void insertNode(Node* currentNode, Node* newNode) {
 if (newNode->key < currentNode->key) {
 if (currentNode->left == nullptr) {
 currentNode->left = newNode;
 } else {
 insertNode(currentNode->left, newNode);
 }
 } else {
 if (currentNode->right == nullptr) {
 currentNode->right = newNode;
 } else {
 insertNode(currentNode->right, newNode);
 }
 }

 // 如果新节点是红色的，则需要旋转和颜色改变 if (newNode->color == 'R') {
 rotateAndColorChange(currentNode, newNode);
 }
 }

 // 销毁函数 void destroy(Node* node) {
 if (node != nullptr) {
 destroy(node->left);
 destroy(node->right);

 delete node;
 }
 }

 // 旋转和颜色改变 void rotateAndColorChange(Node* currentNode, Node* newNode) {
 // 如果新节点的父节点是黑色的，则不需要进行任何操作 if (currentNode->color == 'B') {
 return;
 }

 // 如果新节点的父节点是红色的，则需要旋转和颜色改变 if (newNode->key < currentNode->key) {
 Node* temp = currentNode->left;
 currentNode->left = newNode->right;

 newNode->right = temp;

 currentNode->color = 'B';
 newNode->color = 'R';

 rotateAndColorChange(currentNode, newNode);
 } else {
 Node* temp = currentNode->right;
 currentNode->right = newNode->left;

 newNode->left = temp;

 currentNode->color = 'B';
 newNode->color = 'R';

 rotateAndColorChange(currentNode, newNode);
 }
 }

 // 打印函数 void print(Node* node) {
 if (node != nullptr) {
 print(node->left);

 cout << "Key: " << node->key << ", Color: " << node->color << endl;

 print(node->right);
 }
 }
};

int main() {
 RedBlackTree tree;

 tree.insert(10);
 tree.insert(20);
 tree.insert(5);
 tree.insert(15);

 cout << "Red Black Tree:" << endl;
 tree.print(tree.root);

 return0;
}