哈喽，各位好！今天我们要一起手搓一个简化版的红黑树std::map，保证大家听完之后，感觉自己也能去写STL了（当然，只是感觉）。
首先，我们要明确目标：我们需要一个类似std::map的东西，它能存储键值对，并且能高效地查找、插入和删除。红黑树就是实现这个目标的绝佳选择，因为它能在最坏情况下保证O(log n)的时间复杂度。
一、红黑树的基础知识：不怕，我用人话讲给你听
红黑树，听起来很高大上，其实就是一种特殊的二叉搜索树。为了保持平衡，它给自己加了一些限制（或者说规则）：
- 每个节点要么是红色，要么是黑色。 就像交通信号灯，非红即黑，简单粗暴。
- 根节点是黑色。 树的根基一定要稳，所以必须是黑色的。
- 每个叶子节点（NIL节点，空节点）是黑色。 这些叶子节点其实就是
nullptr，也是黑色的。 - 如果一个节点是红色，那么它的两个子节点都是黑色。 红色节点不能连在一起，不然就乱套了。想象一下红色的多米诺骨牌不能连续摆放。
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。 这条规则保证了树的平衡性。我们把这个黑色节点的数量叫做“黑高”。
这些规则确保了红黑树不会退化成一个链表，从而保证了查找、插入和删除的效率。
二、代码框架：先搭个骨架出来
在开始填充细节之前，我们先搭好整个红黑树map的框架。
#include <iostream>
template <typename Key, typename Value>
class RBTreeMap {
private:
struct Node {
Key key;
Value value;
Node* parent;
Node* left;
Node* right;
bool color; // true: red, false: black
Node(const Key& k, const Value& v) : key(k), value(v), parent(nullptr), left(nullptr), right(nullptr), color(true) {}
};
Node* root;
Node* nil; // Sentinel node
public:
RBTreeMap();
~RBTreeMap();
Value& operator[](const Key& key); // 查找和插入
// Other methods (insert, remove, find, etc.) will be added later
private:
// Helper functions (leftRotate, rightRotate, fixInsert, etc.) will be added later
};这里我们定义了一个RBTreeMap类，它有两个模板参数：Key是键的类型，Value是值的类型。Node结构体表示红黑树的节点，包含键、值、父节点、左右子节点以及颜色。root指向根节点，nil是一个哨兵节点，用来简化代码，它扮演了nullptr的角色。
三、构造函数和析构函数：初始化和清理
template <typename Key, typename Value>
RBTreeMap<Key, Value>::RBTreeMap() {
nil = new Node(Key(), Value()); // Dummy node. Need a default constructor for Key and Value
nil->color = false; // NIL node is always black
root = nil;
}
template <typename Key, typename Value>
RBTreeMap<Key, Value>::~RBTreeMap() {
// Recursive helper function to delete nodes
std::function<void(Node*)> destroy_tree = [&](Node* node) {
if (node != nil) {
destroy_tree(node->left);
destroy_tree(node->right);
delete node;
}
};
destroy_tree(root);
delete nil; // Don't forget to delete the sentinel node
}构造函数初始化root为nil，并创建一个nil节点。析构函数递归地删除所有节点，并最后删除nil节点。 注意，这里我们需要Key和Value类型具有默认构造函数，因为创建nil节点的时候需要用到。
四、查找和插入：operator[]的妙用
operator[]是std::map的核心功能之一，它既能查找，又能插入。
template <typename Key, typename Value>
Value& RBTreeMap<Key, Value>::operator[](const Key& key) {
Node* current = root;
Node* parent = nil;
// Search for the key
while (current != nil) {
parent = current;
if (key < current->key) {
current = current->left;
} else if (key > current->key) {
current = current->right;
} else {
// Key found, return the value
return current->value;
}
}
// Key not found, insert a new node
Node* newNode = new Node(key, Value());
newNode->parent = parent;
newNode->left = nil;
newNode->right = nil;
if (parent == nil) {
// Tree is empty
root = newNode;
} else if (key < parent->key) {
parent->left = newNode;
} else {
parent->right = newNode;
}
fixInsert(newNode); // Maintain red-black tree properties
return newNode->value;
}这段代码首先在树中查找键为key的节点。如果找到，就返回该节点的value的引用。如果没找到，就创建一个新的节点，并将其插入到树中。然后，调用fixInsert函数来维护红黑树的性质。
五、维护红黑树性质：fixInsert是关键
fixInsert函数是红黑树插入操作中最复杂的部分，它负责在插入新节点后，通过旋转和重新着色来保持红黑树的性质。
template <typename Key, typename Value>
void RBTreeMap<Key, Value>::fixInsert(Node* z) {
while (z->parent->color == true) { // While parent is red
if (z->parent == z->parent->parent->left) { // Parent is left child
Node* y = z->parent->parent->right; // Uncle
if (y->color == true) { // Case 1: Uncle is red
z->parent->color = false; // Parent becomes black
y->color = false; // Uncle becomes black
z->parent->parent->color = true; // Grandparent becomes red
z = z->parent->parent; // Move z up the tree
} else { // Case 2: Uncle is black
if (z == z->parent->right) { // z is right child
z = z->parent; // Move z to parent
leftRotate(z); // Left rotate parent
}
// Case 3: z is left child
z->parent->color = false; // Parent becomes black
z->parent->parent->color = true; // Grandparent becomes red
rightRotate(z->parent->parent); // Right rotate grandparent
}
} else { // Parent is right child (symmetric to the above)
Node* y = z->parent->parent->left; // Uncle
if (y->color == true) { // Case 1: Uncle is red
z->parent->color = false; // Parent becomes black
y->color = false; // Uncle becomes black
z->parent->parent->color = true; // Grandparent becomes red
z = z->parent->parent; // Move z up the tree
} else { // Case 2: Uncle is black
if (z == z->parent->left) { // z is left child
z = z->parent; // Move z to parent
rightRotate(z); // Right rotate parent
}
// Case 3: z is right child
z->parent->color = false; // Parent becomes black
z->parent->parent->color = true; // Grandparent becomes red
leftRotate(z->parent->parent); // Left rotate grandparent
}
}
}
root->color = false; // Root must always be black
}这个函数的核心思想是，如果插入一个红色节点导致红红相邻，就需要进行调整。调整的方式有两种：重新着色和旋转。
- Case 1：叔叔节点是红色。 这种情况下，只需要把父节点、叔叔节点都变成黑色，祖父节点变成红色，然后把
z指向祖父节点，继续向上调整。 - Case 2 & 3：叔叔节点是黑色。 这种情况下，需要进行旋转。如果
z是父节点的右孩子，先对父节点进行左旋，然后把z指向父节点。接下来，把父节点变成黑色，祖父节点变成红色，然后对祖父节点进行右旋。如果z是父节点的左孩子，则直接把父节点变成黑色，祖父节点变成红色，然后对祖父节点进行右旋。 （对称情况类似）
六、旋转：leftRotate和rightRotate
旋转是红黑树调整平衡的关键操作，它能改变节点的父子关系，从而调整树的结构。
template <typename Key, typename Value>
void RBTreeMap<Key, Value>::leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nil) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
template <typename Key, typename Value>
void RBTreeMap<Key, Value>::rightRotate(Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == nil) {
root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}这两个函数实现了左旋和右旋操作。它们都接受一个节点作为参数，并改变该节点及其子节点的父子关系。 简单来说，左旋就是把一个节点往左边“拉”，右旋就是往右边“拉”。
七、其他操作：删除和查找
除了插入之外，红黑树还需要支持删除和查找操作。删除操作比插入操作更复杂，因为它需要考虑更多的边界情况。这里我们只给出查找的实现，删除的实现留给大家作为练习。
template <typename Key, typename Value>
Node* RBTreeMap<Key, Value>::find(const Key& key) {
Node* current = root;
while (current != nil) {
if (key < current->key) {
current = current->left;
} else if (key > current->key) {
current = current->right;
} else {
return current; // Key found
}
}
return nullptr; // Key not found
}查找操作很简单，只需要从根节点开始，根据键的大小关系，沿着树向下搜索即可。
八、测试代码：验证我们的成果
为了验证我们的RBTreeMap是否工作正常，我们可以编写一些测试代码。
#include <iostream>
#include <string>
int main() {
RBTreeMap<int, std::string> myMap;
myMap[1] = "apple";
myMap[2] = "banana";
myMap[3] = "orange";
std::cout << "myMap[1]: " << myMap[1] << std::endl;
std::cout << "myMap[2]: " << myMap[2] << std::endl;
std::cout << "myMap[3]: " << myMap[3] << std::endl;
std::cout << "myMap[4]: " << myMap[4] << std::endl; // Inserts a new element
RBTreeMap<std::string, int> stringMap;
stringMap["hello"] = 10;
stringMap["world"] = 20;
std::cout << "stringMap["hello"]: " << stringMap["hello"] << std::endl;
std::cout << "stringMap["world"]: " << stringMap["world"] << std::endl;
return 0;
}这段代码创建了一个RBTreeMap，并插入了一些键值对。然后，它输出了这些键值对的值，并插入一个新的键值对。
九、总结：红黑树，没那么可怕
通过这次手搓红黑树std::map，我们了解了红黑树的基本原理和实现方式。虽然红黑树的实现比较复杂，但只要掌握了它的核心思想，就可以轻松地应对。
| 特性 | 描述 |
|---|---|
| 平衡性 | 红黑树是一种自平衡的二叉搜索树，它通过旋转和重新着色来保持树的平衡，从而保证了查找、插入和删除操作的效率。 |
| 时间复杂度 | 红黑树的查找、插入和删除操作的时间复杂度都是O(log n)，其中n是树中节点的数量。 |
| 空间复杂度 | 红黑树的空间复杂度是O(n)，因为需要存储每个节点的信息。 |
| 实现难度 | 红黑树的实现比较复杂，需要考虑各种边界情况。 |
| 应用场景 | 红黑树广泛应用于各种需要高效查找、插入和删除操作的场景，例如数据库索引、内存管理、以及STL中的std::map和std::set。 |
这次我们实现了一个简化版的std::map，它只支持插入和查找操作。如果想要实现一个完整的std::map，还需要添加删除操作，以及迭代器等功能。 这些就留给大家自己去探索吧！
记住，编程就像盖房子，先搭框架，再填充细节。希望大家通过这次学习，对红黑树有更深入的理解，也能自己动手实现更复杂的数据结构。 下次有机会，我们再一起手搓一个更复杂的STL容器！