# C++紅黑樹(shù)封裝實(shí)戰(zhàn)：實(shí)現(xiàn)簡(jiǎn)易map與set容器
紅黑樹(shù)作為一種自平衡的二叉搜索樹(shù)，是C++標(biāo)準(zhǔn)庫(kù)中map和set容器的底層實(shí)現(xiàn)。本文將詳細(xì)介紹如何使用紅黑樹(shù)封裝實(shí)現(xiàn)簡(jiǎn)易的mymap和myset容器。
## 紅黑樹(shù)基礎(chǔ)概念
紅黑樹(shù)通過(guò)特定的著色規(guī)則和旋轉(zhuǎn)操作維持平衡，確保最壞情況下的操作時(shí)間復(fù)雜度為O(log n)。紅黑樹(shù)滿(mǎn)足以下性質(zhì)：
1. 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色
2. 根節(jié)點(diǎn)是黑色
3. 所有葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）都是黑色
4. 紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色
5. 從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的路徑包含相同數(shù)量的黑色節(jié)點(diǎn)
## 紅黑樹(shù)節(jié)點(diǎn)設(shè)計(jì)
首先定義紅黑樹(shù)節(jié)點(diǎn)的基本結(jié)構(gòu)：
```cpp
enum Color { RED, BLACK };
template<typename T>
struct RBTreeNode {
? ? T data;
? ? Color color;
? ? RBTreeNode* left;
? ? RBTreeNode* right;
? ? RBTreeNode* parent;
? ? RBTreeNode(const T& val, Color c = RED)
? ? ? ? : data(val), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};
```
## 紅黑樹(shù)核心實(shí)現(xiàn)
### 基本框架
```cpp
template<typename K, typename V, typename KeyOfValue>
class RBTree {<"8B.2597.HK">
public:
? ? using Node = RBTreeNode<V>;
? ? RBTree() : root(nullptr), size_(0) {}
? ? ~RBTree() { clear(); }
? ? // 基本接口
? ? bool insert(const V& value);
? ? bool erase(const K& key);
? ? Node* find(const K& key) const;
? ? void clear();
? ? size_t size() const { return size_; }
? ? bool empty() const { return size_ == 0; }
private:
? ? Node* root;
? ? size_t size_;
? ? KeyOfValue keyOfValue;
? ? // 內(nèi)部輔助函數(shù)
? ? void leftRotate(Node* x);
? ? void rightRotate(Node* y);
? ? void insertFixup(Node* z);
? ? void eraseFixup(Node* x);
? ? Node* minimum(Node* node) const;
? ? Node* maximum(Node* node) const;
? ? void transplant(Node* u, Node* v);
? ? void destroy(Node* node);
};
```
### 旋轉(zhuǎn)操作
旋轉(zhuǎn)是維持紅黑樹(shù)平衡的關(guān)鍵操作：
```cpp
template<typename K, typename V, typename KeyOfValue>
void RBTree<K, V, KeyOfValue>::leftRotate(Node* x) {
? ? Node* y = x->right;
? ? x->right = y->left;
? ? if (y->left != nullptr) {
? ? ? ? y->left->parent = x;
? ? }
? ? y->parent = x->parent;
? ? if (x->parent == nullptr) {
? ? ? ? root = y<"2J.2597.HK">;
? ? } else if (x == x->parent->left) {
? ? ? ? x->parent->left = y;
? ? } else {
? ? ? ? x->parent->right = y;
? ? }
? ? y->left = x;
? ? x->parent = y;
}
template<typename K, typename V, typename KeyOfValue>
void RBTree<K, V, KeyOfValue>::rightRotate(Node* y) {
? ? Node* x = y->left;
? ? y->left = x->right;
? ? if (x->right != nullptr) {
? ? ? ? x->right->parent = y;
? ? }
? ? x->parent = y->parent;
? ? if (y->parent == nullptr) {
? ? ? ? root = x;
? ? } else if (y == y->parent->right) {
? ? ? ? y->parent->right = x;
? ? } else {
? ? ? ? y->parent->left = x;
? ? }
? ? x->right = y;
? ? y->parent = x;
}
```
### 插入操作
```cpp
template<typename K, typename V, typename KeyOfValue>
bool RBTree<K, V, KeyOfValue>::insert(const V& value) {
? ? Node* z = new Node(value);
? ? Node* y = nullptr;
? ? Node* x = root;
? ? // 標(biāo)準(zhǔn)BST插入
? ? while (x != nullptr) {
? ? ? ? y = x;
? ? ? ? if (keyOfValue(z->data) < keyOfValue(x->data)) {
? ? ? ? ? ? x = x->left;
? ? ? ? } else if (keyOfValue(z->data) > keyOfValue(x->data)) {
? ? ? ? ? ? x = x->right;
? ? ? ? } else {
? ? ? ? ? ? // 鍵值已存在
? ? ? ? ? ? delete z;
? ? ? ? ? ? return false;
? ? ? ? }
? ? }
? ? z->parent = y;
? ? if (y == nullptr) {
? ? ? ? root = z;
? ? } else if (keyOfValue(z->data) < keyOfValue(y->data)) {
? ? ? ? y->left = z<"5L.2597.HK">;
? ? } else {
? ? ? ? y->right = z;
? ? }
? ? // 插入修復(fù)
? ? insertFixup(z);
? ? size_++;
? ? return true;
}
template<typename K, typename V, typename KeyOfValue>
void RBTree<K, V, KeyOfValue>::insertFixup(Node* z) {
? ? while (z->parent != nullptr && z->parent->color == RED) {
? ? ? ? if (z->parent == z->parent->parent->left) {
? ? ? ? ? ? Node* y = z->parent->parent->right;
? ? ? ? ? ? if (y != nullptr && y->color == RED) {
? ? ? ? ? ? ? ? // 情況1：叔節(jié)點(diǎn)為紅色
? ? ? ? ? ? ? ? z->parent->color = BLACK;
? ? ? ? ? ? ? ? y->color = BLACK;
? ? ? ? ? ? ? ? z->parent->parent->color = RED;
? ? ? ? ? ? ? ? z = z->parent->parent;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? if (z == z->parent->right) {
? ? ? ? ? ? ? ? ? ? // 情況2：z是右孩子
? ? ? ? ? ? ? ? ? ? z = z->parent;
? ? ? ? ? ? ? ? ? ? leftRotate(z);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? // 情況3：z是左孩子
? ? ? ? ? ? ? ? z->parent->color = BLACK;
? ? ? ? ? ? ? ? z->parent->parent->color = RED;
? ? ? ? ? ? ? ? rightRotate(z->parent->parent);
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? // 對(duì)稱(chēng)情況
? ? ? ? ? ? Node* y = z->parent->parent->left;
? ? ? ? ? ? if (y != nullptr && y->color == RED) {
? ? ? ? ? ? ? ? z->parent->color = BLACK;
? ? ? ? ? ? ? ? y->color = BLACK;
? ? ? ? ? ? ? ? z->parent->parent->color = RED;
? ? ? ? ? ? ? ? z = z->parent->parent;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? if (z == z->parent->left) {
? ? ? ? ? ? ? ? ? ? z = z->parent;
? ? ? ? ? ? ? ? ? ? rightRotate(z);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? z->parent->color = BLACK;
? ? ? ? ? ? ? ? z->parent->parent->color = RED;
? ? ? ? ? ? ? ? leftRotate(z->parent->parent);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? root->color = BLACK;
}
```
## 迭代器實(shí)現(xiàn)
為容器提供迭代器支持：
```cpp
template<typename T>
class RBTIterator {
public:
? ? using Node = RBTreeNode<T>;
? ? RBTIterator(Node* node = nullptr) : current(node) {}
? ? T& operator*() const { return current->data; }
? ? T* operator->() const { return &(current->data); }
? ? RBTIterator& operator++() {
? ? ? ? if (current->right != nullptr) {
? ? ? ? ? ? current = current->right;
? ? ? ? ? ? while (current->left != nullptr) {
? ? ? ? ? ? ? ? current = current->left;
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? Node* p = current->parent;
? ? ? ? ? ? while (p != nullptr && current == p->right) {
? ? ? ? ? ? ? ? current = p;
? ? ? ? ? ? ? ? p = p->parent;
? ? ? ? ? ? }
? ? ? ? ? ? current = p;
? ? ? ? }
? ? ? ? return *this;
? ? }
? ? bool operator==(const RBTIterator& other) const {
? ? ? ? return current == other.current;
? ? }
? ? bool operator!=(const RBTIterator& other) const {
? ? ? ? return !(*this == other)<"9S.2597.HK">;
? ? }
private:
? ? Node* current;
};
```
## myset容器實(shí)現(xiàn)
基于紅黑樹(shù)封裝set容器：
```cpp
template<typename K>
class myset {
private:
? ? struct SetKeyOfValue {
? ? ? ? const K& operator()(const K& key) const { return key; }
? ? };
? ? using TreeType = RBTree<K, K, SetKeyOfValue>;
public:
? ? using iterator = RBTIterator<K>;
? ? using const_iterator = RBTIterator<const K>;
? ? myset() : tree() {}
? ? // 容量相關(guān)
? ? bool empty() const { return tree.empty(); }
? ? size_t size() const { return tree.size(); }
? ? // 修改操作
? ? bool insert(const K& key) { return tree.insert(key); }
? ? bool erase(const K& key) { return tree.erase(key); }
? ? void clear() { tree.clear(); }
? ? // 查找操作
? ? iterator find(const K& key) {
? ? ? ? return iterator(tree.find(key));
? ? }
? ? const_iterator find(const K& key) const {
? ? ? ? return const_iterator(tree.find(key));
? ? }
? ? // 迭代器
? ? iterator begin() {
? ? ? ? return iterator(tree.minimum(tree.getRoot()));
? ? }
? ? iterator end() { return iterator(nullptr); }
? ? const_iterator begin() const {
? ? ? ? return const_iterator(tree.minimum(tree.getRoot()));
? ? }
? ? const_iterator end() const { return const_iterator(nullptr); }
private:
? ? TreeType tree;
};
```
## mymap容器實(shí)現(xiàn)
基于紅黑樹(shù)封裝map容器：
```cpp
template<typename K, typename V>
class mymap {
private:
? ? using ValueType = std::pair<const K, V>;
? ? struct MapKeyOfValue {
? ? ? ? const K& operator()(const ValueType& val) const { return val.first; }
? ? };
? ? using TreeType = RBTree<K, ValueType, MapKeyOfValue>;
public:
? ? using iterator = RBTIterator<ValueType>;
? ? using const_iterator = RBTIterator<const ValueType>;
? ? mymap() : tree() {}
? ? // 元素訪(fǎng)問(wèn)
? ? V& operator[](const K& key) {
? ? ? ? auto it = find(key);
? ? ? ? if (it == end()) {
? ? ? ? ? ? auto result = insert(std::make_pair(key, V()));
? ? ? ? ? ? it = result.first;
? ? ? ? }
? ? ? ? return it->second;
? ? }
? ? // 修改操作
? ? std::pair<iterator, bool> insert(const ValueType& value) {
? ? ? ? bool inserted = tree.insert(value);
? ? ? ? return std::make_pair(find(value.first), inserted);
? ? }
? ? bool erase(const K& key) { return tree.erase(key); }
? ? void clear() { tree.clear(); }
? ? // 查找操作
? ? iterator find(const K& key) {
? ? ? ? return iterator(tree.find(key));
? ? }
? ? const_iterator find(const K& key) const {
? ? ? ? return const_iterator(tree.find(key));
? ? }
? ? // 容量相關(guān)
? ? bool empty() const { return tree.empty(); }
? ? size_t size() const { return tree.size(); }
? ? // 迭代器
? ? iterator begin()<"3F.2597.HK"> {
? ? ? ? return iterator(tree.minimum(tree.getRoot()));
? ? }
? ? iterator end() { return iterator(nullptr); }
? ? const_iterator begin() const {
? ? ? ? return const_iterator(tree.minimum(tree.getRoot()));
? ? }
? ? const_iterator end() const { return const_iterator(nullptr); }
private:
? ? TreeType tree;
};
```
## 刪除操作實(shí)現(xiàn)
紅黑樹(shù)的刪除操作相對(duì)復(fù)雜，需要仔細(xì)處理各種情況：
```cpp
template<typename K, typename V, typename KeyOfValue>
bool RBTree<K, V, KeyOfValue>::erase(const K& key) {
? ? Node* z = find(key);
? ? if (z == nullptr) return false;
? ? Node* y = z;
? ? Node* x = nullptr;
? ? Color y_original_color = y->color;
? ? if (z->left == nullptr) {
? ? ? ? x = z->right;
? ? ? ? transplant(z, z->right);
? ? } else if (z->right == nullptr) {
? ? ? ? x = z->left;
? ? ? ? transplant(z, z->left);
? ? } else {
? ? ? ? y = minimum(z->right);
? ? ? ? y_original_color = y->color;
? ? ? ? x = y->right;
? ? ? ? if (y->parent == z) {
? ? ? ? ? ? if (x != nullptr) x->parent = y;
? ? ? ? } else {
? ? ? ? ? ? transplant(y, y->right);
? ? ? ? ? ? y->right = z->right;
? ? ? ? ? ? if (y->right != nullptr) y->right->parent = y;
? ? ? ? }
? ? ? ? transplant(z, y);
? ? ? ? y->left = z->left;
? ? ? ? y->left->parent = y;
? ? ? ? y->color = z->color;
? ? }
? ? if (y_original_color == BLACK && x != nullptr) {
? ? ? ? eraseFixup(x);
? ? }
? ? delete z;
? ? size_--;
? ? return true;
}
```
## 使用示例
測(cè)試實(shí)現(xiàn)的mymap和myset容器：
```cpp
#include <iostream>
#include <string>
void test_mymap() {
? ? mymap<std::string, int> age_map;
? ? // 插入元素
? ? age_map.insert({"Alice", 25});
? ? age_map.insert({"Bob", 30});
? ? age_map["Charlie"] = 35;
? ? // 訪(fǎng)問(wèn)元素
? ? std::cout << "Alice's age: " << age_map["Alice"] << std::endl;
? ? // 遍歷
? ? for (const auto& pair : age_map) {
? ? ? ? std::cout << pair.first << ": " << pair.second << std::endl;
? ? }
? ? // 查找
? ? auto it = age_map.find("Bob");
? ? if (it != age_map.end()) {
? ? ? ? std::cout << "Found Bob, age: " << it->second << std::endl;
? ? }
}
void test_myset() {
? ? myset<int> number_set;
? ? number_set.insert(10);
? ? number_set.insert(20);
? ? number_set.insert(30);
? ? number_set.insert(20); // 重復(fù)元素，不會(huì)插入
? ? for (const auto& num : number_set) {
? ? ? ? std::cout << num << " ";
? ? }
? ? std::cout << std::endl;
? ? std::cout << "Set size: " << number_set.size() << std::endl;
}
int main() {
? ? test_mymap();
? ? test_myset();
? ? return 0;
}
```
## 性能分析與優(yōu)化
### 時(shí)間復(fù)雜度分析
- 插入操作：O(log n)
- 刪除操作：O(log n)
- 查找操作：O(log n)
- 遍歷操作：O(n)
### 內(nèi)存管理優(yōu)化
```cpp
// 添加內(nèi)存池支持
template<typename T>
class RBTreeMemoryPool {
private:
? ? std::vector<RBTreeNode<T>*> nodes;
? ? size_t current_index;
public:
? ? RBTreeNode<T>* allocate(const T& value, Color color) {
? ? ? ? if (current_index >= nodes.size())<"6P.2597.HK"> {
? ? ? ? ? ? nodes.push_back(new RBTreeNode<T>(value, color));
? ? ? ? } else {
? ? ? ? ? ? nodes[current_index]->data = value;
? ? ? ? ? ? nodes[current_index]->color = color;
? ? ? ? ? ? nodes[current_index]->left = nullptr;
? ? ? ? ? ? nodes[current_index]->right = nullptr;
? ? ? ? ? ? nodes[current_index]->parent = nullptr;
? ? ? ? }
? ? ? ? return nodes[current_index++];
? ? }
? ? void deallocate(RBTreeNode<T>* node) {
? ? ? ? // 簡(jiǎn)單的內(nèi)存池，實(shí)際可以更復(fù)雜
? ? }
};
```
## 總結(jié)
通過(guò)封裝紅黑樹(shù)實(shí)現(xiàn)mymap和myset容器，我們深入理解了關(guān)聯(lián)式容器的內(nèi)部機(jī)制。紅黑樹(shù)通過(guò)精妙的平衡策略，在各種操作場(chǎng)景下都能保持良好的性能表現(xiàn)。
實(shí)現(xiàn)過(guò)程中需要注意的關(guān)鍵點(diǎn)包括：旋轉(zhuǎn)操作的正確處理、插入刪除后的平衡調(diào)整、迭代器的正確實(shí)現(xiàn)以及內(nèi)存管理的優(yōu)化。這種底層實(shí)現(xiàn)的理解對(duì)于編寫(xiě)高性能的C++程序和深入理解標(biāo)準(zhǔn)庫(kù)容器具有重要意義。
