C++红黑树封装map和set详解

一、核心设计思路

红黑树作为底层数据结构，通过模板特化实现map和set的差异化封装：

template <typename Key, typename Value>
class RBTreeMap { /* 键值对存储 */ };

template <typename Key>
class RBTreeSet { /* 单键存储 */ };

二、节点结构设计

1. 统一基础节点：

enum Color { RED, BLACK };

template <typename T>
struct RBTreeNode {
    T data;
    Color color;
    RBTreeNode* left;
    RBTreeNode* right;
    RBTreeNode* parent;
};

1. 特化节点类型：

// Set节点
template <typename Key>
struct SetNode : RBTreeNode<Key> { /* 仅存储Key */ };

// Map节点
template <typename Key, typename Value>
struct MapNode : RBTreeNode<std::pair<Key, Value>> { 
    Value& get_value() { return data.second; }
};

三、核心操作实现

1. 插入修复（双红修正）：

   • 情况1：叔节点为红

   void fixInsertCase1(Node* node) {
       uncle->color = BLACK;
       parent->color = BLACK;
       grandparent->color = RED;
       fixInsert(grandparent);
   }
   

   • 情况2/3：叔节点为黑（LL/RR型）

   void fixInsertCase2(Node* node) {
       if (node == parent->left) {
           rotateRight(grandparent);
       } else {
           rotateLeft(grandparent);
       }
       swapColor(parent, grandparent);
   }
   

2. 左旋操作：

void rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    
    y->parent = x->parent;
    if (!x->parent) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    
    y->left = x;
    x->parent = y;
}

四、容器接口封装

1. set接口实现：

template <typename Key>
class RedBlackSet {
public:
    void insert(const Key& key) {
        auto node = new SetNode<Key>(key);
        tree.insert(node);
    }
    
    bool contains(const Key& key) const {
        return tree.search(key) != nullptr;
    }
private:
    RBTree<Key> tree;
};

1. map接口实现：

template <typename Key, typename Value>
class RedBlackMap {
public:
    Value& operator[](const Key& key) {
        auto node = tree.search(key);
        if (!node) {
            node = new MapNode<Key, Value>(key, Value());
            tree.insert(node);
        }
        return node->get_value();
    }
private:
    RBTree<std::pair<Key, Value>> tree;
};

五、迭代器设计

template <typename Node>
class TreeIterator {
public:
    TreeIterator& operator++() {
        if (current->right) {
            current = minNode(current->right);
        } else {
            while (current->parent && current == current->parent->right) {
                current = current->parent;
            }
            current = current->parent;
        }
        return *this;
    }
private:
    Node* minNode(Node* node) const {
        while (node->left) node = node->left;
        return node;
    }
    Node* current;
};

六、性能分析

1. 时间复杂度：
   • 插入/删除：$O(\log n)$
   • 查找：$O(\log n)$
2. 空间复杂度：$O(n)$

七、关键技巧总结

1. 模板特化：通过std::conditional选择节点类型

   using NodeType = std::conditional_t<is_map, 
                    MapNode<Key, Value>, 
                    SetNode<Key>>;
   

2. 颜色标记：使用枚举确保红黑树性质
3. 迭代器失效：插入/删除操作仅影响局部指针
4. 内存管理：使用RAII技术自动释放节点内存

完整实现需处理边界条件（如空树、根节点变色等），建议结合《算法导论》红黑树章节实现删除操作的修正逻辑。