🚀C++ 红黑树与 STL 关联容器详解

C++
约 48 分钟阅读

阅读量:9次
STL

1. 红黑树基础概念

1.1 红黑树性质

红黑树是一种自平衡的二叉搜索树，满足以下性质：

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 每个叶子节点（NIL）是黑色
  4. 红色节点的子节点必须是黑色（不能有连续的红色节点）
  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

1.2 红黑树在 STL 中的应用

STL 中的 set, map, multiset, multimap 通常使用红黑树实现，保证操作的时间复杂度为 O(log n)。

2. STL 中的红黑树容器

2.1 set - 基于红黑树的有序集合

#include <set>
#include <iostream>

void set_example() {
    std::set<int> rb_set;
    
    // 插入元素
    rb_set.insert(5);
    rb_set.insert(2);
    rb_set.insert(8);
    rb_set.insert(1);
    rb_set.insert(5);  // 重复元素，不会被插入
    
    // 遍历（自动排序）
    std::cout << "Set elements: ";
    for (int val : rb_set) {
        std::cout << val << " ";  // 输出: 1 2 5 8
    }
    std::cout << std::endl;
    
    // 查找
    auto it = rb_set.find(5);
    if (it != rb_set.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // 范围查找
    auto lower = rb_set.lower_bound(3);  // 第一个 >= 3 的元素
    auto upper = rb_set.upper_bound(6);  // 第一个 > 6 的元素
    
    std::cout << "Range [3,6]: ";
    for (auto i = lower; i != upper; ++i) {
        std::cout << *i << " ";  // 输出: 5
    }
    std::cout << std::endl;
    
    // 删除
    rb_set.erase(2);
    std::cout << "After erase: ";
    for (int val : rb_set) {
        std::cout << val << " ";  // 输出: 1 5 8
    }
    std::cout << std::endl;
}

2.2 map - 基于红黑树的有序键值对

#include <map>
#include <string>

void map_example() {
    std::map<std::string, int> rb_map;
    
    // 插入元素
    rb_map["Alice"] = 95;
    rb_map["Bob"] = 87;
    rb_map["Charlie"] = 92;
    rb_map.insert({"David", 88});
    
    // 遍历（按键排序）
    std::cout << "Map contents:" << std::endl;
    for (const auto& pair : rb_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 输出（按字母排序）:
    // Alice: 95
    // Bob: 87  
    // Charlie: 92
    // David: 88
    
    // 查找和访问
    if (rb_map.find("Alice") != rb_map.end()) {
        std::cout << "Alice's score: " << rb_map["Alice"] << std::endl;
    }
    
    // 使用 at() 安全访问（会检查边界）
    try {
        std::cout << "Bob's score: " << rb_map.at("Bob") << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Key not found" << std::endl;
    }
    
    // 删除元素
    rb_map.erase("Bob");
}

2.3 multiset 和 multimap - 允许重复元素的红黑树

#include <set>
#include <map>

void multi_example() {
    // multiset - 允许重复元素
    std::multiset<int> rb_multiset = {1, 2, 2, 3, 3, 3, 4};
    
    std::cout << "Multiset elements: ";
    for (int val : rb_multiset) {
        std::cout << val << " ";  // 输出: 1 2 2 3 3 3 4
    }
    std::cout << std::endl;
    
    // 计数重复元素
    std::cout << "Count of 3: " << rb_multiset.count(3) << std::endl;  // 输出: 3
    
    // multimap - 允许重复键
    std::multimap<std::string, int> rb_multimap;
    rb_multimap.insert({"Alice", 95});
    rb_multimap.insert({"Alice", 98});
    rb_multimap.insert({"Bob", 87});
    
    // 查找所有相同键的值
    auto range = rb_multimap.equal_range("Alice");
    std::cout << "Alice's scores: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";  // 输出: 95 98
    }
    std::cout << std::endl;
}

3. 红黑树操作详解

3.1 插入操作

#include <set>
#include <vector>

void insertion_analysis() {
    std::set<int> tree;
    std::vector<int> data = {10, 20, 5, 15, 25, 3, 7, 17, 23, 27};
    
    for (int val : data) {
        auto result = tree.insert(val);
        
        // insert() 返回 pair<iterator, bool>
        if (result.second) {
            std::cout << "Inserted: " << val << std::endl;
        } else {
            std::cout << "Duplicate: " << val << std::endl;
        }
    }
    
    // 分析插入后的树结构
    std::cout << "Tree size: " << tree.size() << std::endl;
    std::cout << "Tree height approx: " << "O(log " << tree.size() << ")" << std::endl;
}

3.2 删除操作

void deletion_analysis() {
    std::set<int> tree = {10, 20, 5, 15, 25, 3, 7, 17, 23, 27};
    
    std::cout << "Before deletion: ";
    for (int val : tree) std::cout << val << " ";
    std::cout << std::endl;
    
    // 删除单个元素
    size_t count = tree.erase(15);
    std::cout << "Deleted " << count << " element(s)" << std::endl;
    
    // 使用迭代器删除
    auto it = tree.find(20);
    if (it != tree.end()) {
        tree.erase(it);
    }
    
    // 删除范围
    auto first = tree.lower_bound(5);
    auto last = tree.upper_bound(17);
    tree.erase(first, last);
    
    std::cout << "After deletion: ";
    for (int val : tree) std::cout << val << " ";
    std::cout << std::endl;
}

4. 自定义比较函数

4.1 使用函数对象

#include <set>
#include <string>

// 自定义比较函数对象
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char c1, char c2) {
                return std::tolower(c1) < std::tolower(c2);
            });
    }
};

void custom_comparator() {
    // 使用自定义比较器的 set
    std::set<std::string, CaseInsensitiveCompare> case_insensitive_set;
    
    case_insensitive_set.insert("Apple");
    case_insensitive_set.insert("banana");
    case_insensitive_set.insert("apple");  // 不会被插入，因为 "Apple" 和 "apple" 被认为相同
    
    std::cout << "Case insensitive set: ";
    for (const auto& str : case_insensitive_set) {
        std::cout << str << " ";  // 输出: Apple banana
    }
    std::cout << std::endl;
}

4.2 使用 Lambda 表达式（C++14+）

#include <set>
#include <functional>

void lambda_comparator() {
    // 使用 lambda 表达式作为比较器
    auto descending = [](int a, int b) { return a > b; };
    
    std::set<int, decltype(descending)> descending_set(descending);
    
    descending_set.insert({1, 2, 3, 4, 5});
    
    std::cout << "Descending set: ";
    for (int val : descending_set) {
        std::cout << val << " ";  // 输出: 5 4 3 2 1
    }
    std::cout << std::endl;
}

5. 性能分析与时间复杂度

5.1 时间复杂度对比

#include <set>
#include <map>
#include <chrono>
#include <random>
#include <iostream>

void performance_analysis() {
    std::set<int> tree;
    std::vector<int> data;
    
    // 生成随机数据
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);
    
    for (int i = 0; i < 10000; ++i) {
        data.push_back(dis(gen));
    }
    
    // 插入性能测试
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int val : data) {
        tree.insert(val);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Insertion time: " << duration.count() << " microseconds" << std::endl;
    std::cout << "Tree size: " << tree.size() << std::endl;
    
    // 查找性能测试
    start = std::chrono::high_resolution_clock::now();
    
    int found_count = 0;
    for (int i = 0; i < 1000; ++i) {
        if (tree.find(dis(gen)) != tree.end()) {
            found_count++;
        }
    }
    
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Search time: " << duration.count() << " microseconds" << std::endl;
    std::cout << "Found " << found_count << " elements" << std::endl;
}

5.2 内存使用分析

#include <memory>
#include <set>

void memory_analysis() {
    // 红黑树节点大致结构（简化）
    struct TreeNode {
        int value;
        bool color;  // 红黑颜色
        TreeNode* left;
        TreeNode* right;
        TreeNode* parent;
    };
    
    std::set<int> tree;
    for (int i = 0; i < 1000; ++i) {
        tree.insert(i);
    }
    
    std::cout << "Theoretical memory usage:" << std::endl;
    std::cout << "Each node: " << sizeof(TreeNode) << " bytes" << std::endl;
    std::cout << "Total nodes: " << tree.size() << std::endl;
    std::cout << "Estimated memory: " << sizeof(TreeNode) * tree.size() << " bytes" << std::endl;
}

6. 高级用法和技巧

6.1 提取节点（C++17）

#if __cplusplus >= 201703L
#include <set>

void node_handling() {
    std::set<int> tree = {1, 2, 3, 4, 5};
    
    // 提取节点（不重新分配内存）
    auto node = tree.extract(3);
    
    if (!node.empty()) {
        std::cout << "Extracted value: " << node.value() << std::endl;
        
        // 修改值并重新插入
        node.value() = 6;
        tree.insert(std::move(node));
    }
    
    std::cout << "After node handling: ";
    for (int val : tree) {
        std::cout << val << " ";  // 输出: 1 2 4 5 6
    }
    std::cout << std::endl;
}
#endif

6.2 合并容器（C++17）

#if __cplusplus >= 201703L
#include <set>

void merge_containers() {
    std::set<int> tree1 = {1, 3, 5};
    std::set<int> tree2 = {2, 4, 6};
    
    std::cout << "Before merge:" << std::endl;
    std::cout << "Tree1: "; for (int v : tree1) std::cout << v << " "; std::cout << std::endl;
    std::cout << "Tree2: "; for (int v : tree2) std::cout << v << " "; std::cout << std::endl;
    
    // 合并两个 set
    tree1.merge(tree2);
    
    std::cout << "After merge:" << std::endl;
    std::cout << "Tree1: "; for (int v : tree1) std::cout << v << " "; std::cout << std::endl;
    std::cout << "Tree2: "; for (int v : tree2) std::cout << v << " "; std::cout << std::endl;
}
#endif

7. 红黑树迭代器详解

7.1 迭代器操作

#include <set>
#include <iterator>

void iterator_operations() {
    std::set<int> tree = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 双向迭代器
    auto it = tree.begin();
    std::cout << "Begin: " << *it << std::endl;
    
    // 前进
    ++it;
    std::advance(it, 3);
    std::cout << "After advance: " << *it << std::endl;
    
    // 后退
    --it;
    std::cout << "After decrement: " << *it << std::endl;
    
    // 计算距离
    auto dist = std::distance(tree.begin(), it);
    std::cout << "Distance from begin: " << dist << std::endl;
    
    // 反向迭代器
    std::cout << "Reverse order: ";
    for (auto rit = tree.rbegin(); rit != tree.rend(); ++rit) {
        std::cout << *rit << " ";  // 输出: 10 9 8 7 6 5 4 3 2 1
    }
    std::cout << std::endl;
}

7.2 安全的迭代器使用

void safe_iterator_usage() {
    std::set<int> tree = {1, 2, 3, 4, 5};
    
    // 安全的删除方式
    for (auto it = tree.begin(); it != tree.end(); ) {
        if (*it % 2 == 0) {
            it = tree.erase(it);  // erase() 返回下一个有效的迭代器
        } else {
            ++it;
        }
    }
    
    std::cout << "After safe deletion: ";
    for (int val : tree) {
        std::cout << val << " ";  // 输出: 1 3 5
    }
    std::cout << std::endl;
}

8. 实际应用案例

8.1 学生成绩管理系统

#include <map>
#include <set>
#include <string>
#include <vector>

class StudentManager {
private:
    std::map<int, std::string> id_to_name;  // 学号到姓名
    std::map<std::string, int> name_to_score;  // 姓名到成绩
    
public:
    void addStudent(int id, const std::string& name, int score) {
        id_to_name[id] = name;
        name_to_score[name] = score;
    }
    
    void printByID() {
        std::cout << "Students by ID:" << std::endl;
        for (const auto& pair : id_to_name) {
            std::cout << "ID: " << pair.first << ", Name: " << pair.second 
                      << ", Score: " << name_to_score[pair.second] << std::endl;
        }
    }
    
    void printTopScores(int n) {
        // 使用 multimap 按成绩排序（允许相同成绩）
        std::multimap<int, std::string, std::greater<int>> score_to_name;
        
        for (const auto& pair : name_to_score) {
            score_to_name.insert({pair.second, pair.first});
        }
        
        std::cout << "Top " << n << " students:" << std::endl;
        int count = 0;
        for (const auto& pair : score_to_name) {
            if (count++ >= n) break;
            std::cout << pair.second << ": " << pair.first << std::endl;
        }
    }
};

void student_management_example() {
    StudentManager manager;
    
    manager.addStudent(101, "Alice", 95);
    manager.addStudent(102, "Bob", 87);
    manager.addStudent(103, "Charlie", 92);
    manager.addStudent(104, "David", 95);  // 相同成绩
    
    manager.printByID();
    std::cout << std::endl;
    manager.printTopScores(3);
}

添加新评论