c++红黑树实现map

红黑树是一种自平衡的二叉搜索树，常用于实现关联容器map。

下面是C++代码示例，实现了一个红黑树类，可以用于实现map：

#include <iostream>
using namespace std;

enum Color {RED, BLACK};

template<typename K,typename V>
class RBNode {
public:
    K key;
    V value;
    Color color;
    RBNode<K,V> *left, *right, *parent;

    RBNode(): color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
    RBNode(K k, V v): color(RED), key(k), value(v), left(nullptr), right(nullptr), parent(nullptr) {}
    RBNode(K k, V v, Color c): color(c), key(k), value(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

template<typename K,typename V>
class RBTree {
public:
    RBTree();
    ~RBTree();
    bool empty() const;
    int size() const;
    void clear();
    void insert(const K& key,const V& value);
    bool find(const K& key);
    void remove(const K& key);
    void printTree() const;

private:
    RBNode<K,V>* root;
    int count;
    void rotateLeft(RBNode<K,V>* node);
    void rotateRight(RBNode<K,V>* node);
    void fixup(RBNode<K,V>* node);
    RBNode<K,V>* minimum(RBNode<K,V>* node);
    void transplant(RBNode<K,V>* u, RBNode<K,V>* v);
    void removeNode(RBNode<K,V>* node);
};

template<typename K,typename V>
RBTree<K,V>::RBTree(): root(nullptr), count(0) {}

template<typename K,typename V>
RBTree<K,V>::~RBTree() {
    clear();
}

template<typename K,typename V>
bool RBTree<K,V>::empty() const {
    return count == 0;
}

template<typename K,typename V>
int RBTree<K,V>::size() const {
    return count;
}

template<typename K,typename V>
void RBTree<K,V>::clear() {
    while (root != nullptr) {
        removeNode(root);
    }
    count = 0;
}

template<typename K,typename V>
void RBTree<K,V>::rotateLeft(RBNode<K,V>* node) {
    RBNode<K,V>* r = node->right;
    node->right = r->left;
    if (r->left != nullptr) r->left->parent = node;
    r->parent = node->parent;
    if (node->parent == nullptr) root = r;
    else if (node == node->parent->left) node->parent->left = r;
    else node->parent->right = r;
    r->left = node;
    node->parent = r;
}

template<typename K,typename V>
void RBTree<K,V>::rotateRight(RBNode<K,V>* node) {
    RBNode<K,V>* l = node->left;
    node->left = l->right;
    if (l->right != nullptr) l->right->parent = node;
    l->parent = node->parent;
    if (node->parent == nullptr) root = l;
    else if (node == node->parent->right) node->parent->right = l;
    else node->parent->left = l;
    l->right = node;
    node->parent = l;
}

template<typename K,typename V>
void RBTree<K,V>::fixup(RBNode<K,V>* node) {
    while (node->parent != nullptr && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            RBNode<K,V>* uncle = node->parent->parent->right;
            if (uncle != nullptr && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    rotateLeft(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotateRight(node->parent->parent);
            }
        } else {
            RBNode<K,V>* uncle = node->parent->parent->left;
            if (uncle != nullptr && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rotateRight(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotateLeft(node->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

template<typename K,typename V>
void RBTree<K,V>::insert(const K& key,const V& value) {
    RBNode<K,V>* node = new RBNode<K,V>(key, value);
    RBNode<K,V>* p = nullptr;
    RBNode<K,V>* q = root;
    while (q != nullptr) {
        p = q;
        if (node->key < q->key) q = q->left;
        else q = q->right;
    }
    node->parent = p;
    if (p == nullptr) root = node;
    else if (node->key < p->key) p->left = node;
    else p->right = node;
    count++;
    fixup(node);
}

template<typename K,typename V>
bool RBTree<K,V>::find(const K& key) {
    RBNode<K,V>* node = root;
    while (node != nullptr) {
        if (key == node->key) return true;
        else if (key < node->key) node = node->left;
        else node = node->right;
    }
    return false;
}

template<typename K,typename V>
void RBTree<K,V>::transplant(RBNode<K,V>* u, RBNode<K,V>* v) {
    if (u->parent == nullptr) root = v;
    else if (u == u->parent->left) u->parent->left = v;
    else u->parent->right = v;
    if (v != nullptr) v->parent = u->parent;
}

template<typename K,typename V>
void RBTree<K,V>::removeNode(RBNode<K,V>* node) {
    if (node == nullptr) return;
    RBNode<K,V>* p = node->parent;
    bool isLeft = (p != nullptr && node == p->left);
    if (node->left == nullptr) {
        transplant(node, node->right);
    } else if (node->right == nullptr) {
        transplant(node, node->left);
    } else {
        RBNode<K,V>* s = minimum(node->right);
        RBNode<K,V>* sp = s->parent;
        isLeft = (s->parent != nullptr && s == s->parent->left);
        if (s->parent != node) {
            transplant(s, s->right);
            s->right = node->right;
            s->right->parent = s;
        }
        transplant(node, s);
        s->left = node->left;
        s->left->parent = s;
        s->color = node->color;
    }
    delete node;
    count--;
    if (isLeft) fixup(p->left);
    else fixup(p->right);
}

template<typename K,typename V>
void RBTree<K,V>::remove(const K& key) {
    RBNode<K,V>* z = root;
    while (z != nullptr) {
        if (z->key == key) {
            removeNode(z);
            return;
        } else if (key < z->key) z = z->left;
        else z = z->right;
    }
}

template<typename K,typename V>
RBNode<K,V>* RBTree<K,V>::minimum(RBNode<K,V>* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

template<typename K,typename V>
void inOrder(RBNode<K,V>* node) {
    if (node == nullptr) return;
    if (node->left != nullptr) inOrder(node->left);
    cout << node->key << "(" << (node->color == RED ? "RED" : "BLACK") << ") ";
    if (node->right != nullptr) inOrder(node->right);
}

template<typename K,typename V>
void RBTree<K,V>::printTree() const {
    inOrder(root);
    cout << endl;
}

int main() {
    RBTree<int,int> tree;
    tree.insert(1,2);
    tree.insert(2,3);
    tree.insert(3,4);
    tree.insert(4,5);
    tree.insert(5,6);
    tree.printTree();
    cout << tree.find(3) << endl;
    tree.remove(3);
    tree.printTree();
    return 0;
}

该示例中包含了插入、查找、删除等基本操作，并支持输出红黑树中所有节点及其颜色，可以用于验证红黑树的正确性。