【C++详解】——红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除节点时会自动调整树的结构，以保持树的平衡性。红黑树是由鲁道夫·贝尔（Rudolf Bayer）在1972年发明的，后来由Leo J. Guibas和Robert Sedgewick在1978年对其进行了改进和完善。

红黑树的特点有以下几点：
1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL节点）是黑色的。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5.从任意节点到其每个叶子节点的路径包含相同数量的黑色节点。

通过这些规则，红黑树可以保持树的高度平衡，使得在最坏情况下，树的高度不会超过2log(n+1)，其中n是树中节点的数量。

下面我们来实现一个简单的红黑树，并对其进行详细解释。

cpp#include <iostream>
using namespace std;

enum Color { RED, BLACK };

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

 Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
 Node* root;

 void rotateLeft(Node* node) {
 Node* 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;
 }

 void rotateRight(Node* node) {
 Node* 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->right) {
 node->parent->right = leftChild;
 } else {
 node->parent->left = leftChild;
 }
 leftChild->right = node;
 node->parent = leftChild;
 }

 void fixViolation(Node* node) {
 Node* parent = nullptr;
 Node* grandParent = nullptr;
 while (node != root && node->color == RED && node->parent->color == RED) {
 parent = node->parent;
 grandParent = parent->parent;
 if (parent == grandParent->left) {
 Node* uncle = grandParent->right;
 if (uncle != nullptr && uncle->color == RED) {
 grandParent->color = RED;
 parent->color = BLACK;
 uncle->color = BLACK;
 node = grandParent;
 } else {
 if (node == parent->right) {
 rotateLeft(parent);
 node = parent;
 parent = node->parent;
 }
 rotateRight(grandParent);
 swap(parent->color, grandParent->color);
 node = parent;
 }
 } else {
 Node* uncle = grandParent->left;
 if (uncle != nullptr && uncle->color == RED) {
 grandParent->color = RED;
 parent->color = BLACK;
 uncle->color = BLACK;
 node = grandParent;
 } else {
 if (node == parent->left) {
 rotateRight(parent);
 node = parent;
 parent = node->parent;
 }
 rotateLeft(grandParent);
 swap(parent->color, grandParent->color);
 node = parent;
 }
 }
 }
 root->color = BLACK;
 }

public:
 RedBlackTree() : root(nullptr) {}

 void insert(int data) {
 Node* newNode = new Node(data);
 Node* parent = nullptr;
 Node* current = root;
 while (current != nullptr) {
 parent = current;
 if (data < current->data) {
 current = current->left;
 } else {
 current = current->right;
 }
 }
 newNode->parent = parent;
 if (parent == nullptr) {
 root = newNode;
 } else if (data < parent->data) {
 parent->left = newNode;
 } else {
 parent->right = newNode;
 }
 fixViolation(newNode);
 }

 void inorderTraversal(Node* node) {
 if (node == nullptr) {
 return;
 }
 inorderTraversal(node->left);
 cout << node->data << " ";
 inorderTraversal(node->right);
 }

 void printInorder() {
 inorderTraversal(root);
 cout << endl;
 }
};

int main() {
 RedBlackTree tree;
 tree.insert(7);
 tree.insert(3);
 tree.insert(18);
 tree.insert(10);
 tree.insert(22);
 tree.insert(8);
 tree.insert(11);
 tree.insert(26);
 tree.insert(2);
 tree.insert(6);

 cout << "Inorder traversal of the Red-Black Tree: ";
 tree.printInorder();

 return0;
}

在上面的代码中，我们首先定义了一个Node结构体，表示红黑树的节点，其中包含数据、颜色、左子节点、右子节点和父节点。然后定义了RedBlackTree类，包含了插入节点、左旋、右旋和修正违反规则的方法。

在插入节点时，我们首先按照二叉搜索树的规则找到插入位置，然后将新节点插入，并调用fixViolation方法修正可能违反红黑树规则的情况。fixViolation方法会根据插入节点的父节点、祖父节点和叔节点的颜色进行不同的旋转操作，以保持红黑树的平衡性。

最后，在main函数中我们创建了一个红黑树对象，并插入了一些节点，然后进行中序遍历输出结果。

红黑树是一种非常重要的数据结构，它在很多高级算法和数据结构中都有应用，如STL中的map和set等。掌握红黑树的原理和实现对于提高编程能力和理解其他数据结构也是非常有帮助的。希望通过本文的介绍，读者能对红黑树有更深入的理解。