map和set的实现(3)——红黑树封装

大大源码 • 2023年3月22日 pm10:36 • 其他

我们前面写的红黑树是k-v结构的，但是set是k结构的，如何保证复用性的情况下进行封装。

学习源码要先看框架，框架看懂了细节就容易多了。

文章目录

红黑树结构的复用

源码的复用框架

RBTree.h

#pragma once
#include <iostream>
using namespace std;
enum Color
{
    RED,
    BLACK
};
template<class T>
struct RBTreeNode
{
    RBTreeNode(const T& x)
        :_left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _data(x),
        _col(RED)
    {}

    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;

    T _data;
    Color _col;
};
//template<class K,class T>
//struct __TreeIteror
//{
//    typedef BRTreeNode<K,V> Node;
//    Node* _node;
//    __TreeIterator(Node* node)
//        :_node(node)
//        {}
//    T _node;
//}
template<class K, class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    RBTree()
        :_root(nullptr)
    {	}
    void Destroy(Node* root)
    {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    ~RBTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
    //拷贝构造和operator[]赋值

    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_data > key)
            {
                cur = cur->_left;
            }
            else if (cur->_data < key)
            {
                cur = cur->_right;
            }
            else {
                return cur;
            }
        }
        return nullptr;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;
        subL->_right = parent;

        Node* grandParent = parent->_parent;

        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else {
            if (grandParent->_left == parent)
            {
                grandParent->_left = subL;
            }
            else {
                grandParent->_right = subL;
            }
            subL->_parent = grandParent;
        }
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL != nullptr) {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* grandparent = parent->_parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else {
            if (grandparent->_left == parent)
            {
                grandparent->_left = subR;
            }
            else {
                grandparent->_right = subR;
            }

            subR->_parent = grandparent;
        }

       
    }
    pair<Node*, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root -> _col= BLACK;
            return make_pair(_root, true);
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_data < data)//如果实现的是multimap这里使用的是<=
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return make_pair(cur, false);
            }
        }
        Node* newnode = new Node(data);
        if (parent->_data < data)
        {
            parent->_right = newnode;
            newnode->_parent = parent;
        }
        else {
            parent->_left = newnode;
            newnode->_parent = parent;
        }
        cur = newnode;

        //如果父亲存在，且颜色为红色，则需要处理
        while (parent && parent->_col == RED)
        {
            //关键看叔叔
            Node* grandfather = parent->_parent; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红

            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //情况一：uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else { //情况 2+3  uncle不存在/uncle存在且为黑
                    if (cur == parent->_left) // 情况2: 单旋
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else { //情况三:双旋
                        RotateL(parent);
                        RotateR(grandfather);

                        cur->_col = BLACK;
                        parent->_col = RED;
                    }

                    break;//旋转完就整棵树变成红黑树了
                }
            }
            else// parent == grandfather -> _right;
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)//情况一:叔叔存在且为红
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    grandfather = cur->_parent;
                }
                else {//情况二+三:叔叔存在且为黑或者不存在
                    if (cur == parent->_right)//情况二:单旋+变色
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完必定搞定
                }
            }
        }

        _root->_col = BLACK;
        return make_pair(newnode, true);
    }
private:
    Node* _root;
};

Map.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K, class V>
    class map
    {
    public:
        bool insert(const pair<const K, V>& kv)
        {
            _t.Insert(kv);
            return true;
        }
    private:
        RBTree< K, pair<const K, V> > _t;
    };
}

Set.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K, class V>
    class set
    {
    public:
        bool insert(const K& k)
        {
            _t.Insert(k);

            return true;
        }
    private:
        RBTree< K, K > _t;

    };
}

main.cc

#include "Map.h"
#include "Set.h"
#include<stdlib.h>

int main()
{
    Y::map<int, int> m;
    m.insert(std::make_pair(1,1));

    Y::set<int, int > s;
    s.insert(1);
}

key和key-value的比较碰到的问题

这样子虽然处理出传的是k-v还是k直接由TreeNode的T决定，但是Insert进行比较的时候就没法比较了。因为不知道传的是key还是key-value。但是最后是编译通过。原因在于pair类型重载了比较，但是这个比较不是我们想要的。

我们要的<是按照first去比。只有key的比较没有value的比较。

库的<比较是：如果first1<first2，为真；first1>=first2，会按照second去比较。

倘若使用库中的比较，我们在find的时候只使用key去比较，并没有second。因此可能导致插入进去的值可能找不到。

那能不能使用重载pair达到效果呢？做不到。

就算重载了左边的是pair右边是key，也不支持比较。还得把key取出来
pair已经实现了

    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_data > key)
            {
                cur = cur->_left;
            }
            else if (cur->_data < key)
            {
                cur = cur->_right;
            }
            else {
                return cur;
            }
        }
        return nullptr;
    }

仿函数实现两种类型的各自比较

我们回去看看源码中是怎么做的？

在传的时候传了select1st和identity。在Tree.h的定义中存了KeyOfValue

我们使用仿函数，在map和set中定义好仿函数类，作为一个模板传给tree，这样一旦遇到了data的比较就使用对其调用仿函数，如果是key就取key，如果是key-value就取first。

虽然不知道存的具体是什么，但是针对具体的key和pair都要处理干净实现需要的功能，这种更高维度的泛型要借助仿函数来实现。

map.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K, class V>
    class map
    {
        //定义内部类
        struct SetKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };
    public:
        bool insert(const pair<const K, V>& kv)
        {
            _t.Insert(kv);
            return true;
        }
    private:
        RBTree< K, pair<const K, V>, SetKeyOfT > _t;
    };
}

set.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K, class V>
    class set
    {
        //定义内部类
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:
        bool insert(const K& k)
        {
            _t.Insert(k);

            return true;
        }
    private:
        RBTree< K, K , SetKeyOfT> _t;

    };
}

RBTree.h

//KeyOfT——仿函数，若T为pair，用于取出T中的first(key)
template<class K, class T , class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    RBTree()
        :_root(nullptr)
    {	}
    void Destroy(Node* root)
    {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    ~RBTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
    //拷贝构造和operator[]赋值

    Node* Find(const K& key)
    {
        KeyOfT kot;
        Node* cur = _root;
        while (cur)
        {
            if ( kot(cur->_data) > key)
            {
                cur = cur->_left;
            }
            else if ( kot(cur->_data) < key)
            {
                cur = cur->_right;
            }
            else {
                return cur;
            }
        }
        return nullptr;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;
        subL->_right = parent;

        Node* grandParent = parent->_parent;

        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else {
            if (grandParent->_left == parent)
            {
                grandParent->_left = subL;
            }
            else {
                grandParent->_right = subL;
            }
            subL->_parent = grandParent;
        }
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL != nullptr) {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* grandparent = parent->_parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else {
            if (grandparent->_left == parent)
            {
                grandparent->_left = subR;
            }
            else {
                grandparent->_right = subR;
            }

            subR->_parent = grandparent;
        }

       
    }
    pair<Node*, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root -> _col= BLACK;
            return make_pair(_root, true);
        }
        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if ( kot( cur->_data ) < kot(data) )//如果实现的是multimap这里使用的是<=
            {
                parent = cur;
                cur = cur->_right;
            }
            else if ( kot( cur->_data ) > kot(data) )
            {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return make_pair(cur, false);
            }
        }
        Node* newnode = new Node(data);
        if ( kot(parent->_data) < kot(data) )
        {
            parent->_right = newnode;
            newnode->_parent = parent;
        }
        else {
            parent->_left = newnode;
            newnode->_parent = parent;
        }
        cur = newnode;

        //如果父亲存在，且颜色为红色，则需要处理
        while (parent && parent->_col == RED)
        {
            //关键看叔叔
            Node* grandfather = parent->_parent; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红

            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //情况一：uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else { //情况 2+3  uncle不存在/uncle存在且为黑
                    if (cur == parent->_left) // 情况2: 单旋
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else { //情况三:双旋
                        RotateL(parent);
                        RotateR(grandfather);

                        cur->_col = BLACK;
                        parent->_col = RED;
                    }

                    break;//旋转完就整棵树变成红黑树了
                }
            }
            else// parent == grandfather -> _right;
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)//情况一:叔叔存在且为红
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    grandfather = cur->_parent;
                }
                else {//情况二+三:叔叔存在且为黑或者不存在
                    if (cur == parent->_right)//情况二:单旋+变色
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完必定搞定
                }
            }
        }

        _root->_col = BLACK;
        return make_pair(newnode, true);
    }
private:
    Node* _root;
};

迭代器的实现

迭代器的结构

RBTree.h

template<class T, class Ref, class Ptr >
struct __TreeIteror
{
    typedef BRTreeNode<T> Node;
    typedef __TreeIterator < T, Ref, Ptr > Self;

    Node* _node;
    __TreeIterator(Node* node)
        :_node(node)
    {}
    Ref operator*()
    {
        return _node->_data;//对于set是key,对于map是pair。T类型
    }
    Ptr operator->()
    {
        return &_node->_data;
    }
    bool operator != (const Self& s) const
    {
        return _node != s->_node;
    }
    //重点
    Self& operator++();   //对于list来说,node=node->_next;
    Self& operator--();
};
template<class K, class T , class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef __TreeIterator < T, T&, T* > iterator;
    typedef __TreeIterator < T, T&, T* > reverse_iterator;
    typedef __TreeIterator < T, const T&, const T* > const_iterator;

    iterator begin()
    {
        Node* left = _root;
        while (left && left->_left)
        {
            left = left->_left;
        }
        return iterator(left);
    }
    iterator end()
    {
        return iterator(nullptr);
    }
    reverse_iterator rbegin()
    {
        Node* right = _root;
        while (right && right->_right)
        {
            right = right->_right;
        }
        return reverse_iterator(right);
    }
    reverse_iterator rend()
    {
        return reverse_iterator(nullptr);
    }
};

Set.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K>
    class set
    {
        //定义内部类
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:

        //平时使用class和typename是一样的，但是这里是不一样的,取的是类模板的类型
        //因为我们先实例化的是set<int>,编译器走到这里的时候 RBTree< K, K, SetKeyOfT >还没被实例化出来，找不到这个类，typename告诉编译器后面等RBTree<>类模板实例化之后再回来这里去对应的实例化的类中去找
        typedef  typename RBTree< K, K, SetKeyOfT >::iterator iterator;
        typedef  typename RBTree< K, K, SetKeyOfT >::reverse_iterator reverse_iterator;
        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }
        reverse_iterator rbegin()
        {
            return _t.rbegin();
        }
        reverse_iterator rend()
        {
            return _t.rend();
        }
        bool insert(const K& k)
        {
            _t.Insert(k);

            return true;
        }
        bool CheckBlance()
        {
            return _t.CheckBlance();
        }
    private:
        RBTree< K, K , SetKeyOfT> _t;
    };
}

operator++/–的实现

带头节点

如何实现++？总不能用非递归的stack来存，迭代器总是使用，这样空间巨大。

看看源码。

源码中使用了increment()和decrement()。

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列。

因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？

能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

不带头节点

operator++

右树不等于空，下一个访问就是右树中，中序的第一个结点（右子树的最左节点）
右树等于空，沿着三叉链往上走，直到father->left==cur结束。
遍历完会回到根节点的parent(nullptr)

因为cur右为空，说明cur所在的子树已经访问完了。若cur==parent->_right说明parent也访问完了，继续往上去找。

operator--

若左子树不为空，下一个访问就是左子树中，中序的最后一个结点(左子树的最右结点)
左子树为空，沿着三叉链往上走，直到father->right==cur结束
遍历完会回到根节点的parent(nullptr)

template<class T, class Ref, class Ptr >
struct __TreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator < T, Ref, Ptr > Self;

    Node* _node;
    __TreeIterator(Node* node)
        :_node(node)
    {}
    Ref operator*()
    {
        return _node->_data;//对于set是key,对于map是pair。T类型
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

    bool operator != (const Self& s) const
    {
        return _node != s._node;
    }

    //重点
    Self& operator++()   //对于list来说,node=node->_next;
    {
        if (_node->_right)
        {
            //下一个访问的就是右树中，中序的第一个结点(最左)
            Node* left = _node->_right;
            while (left->_left)
            {
                left = left->_left;
            }

            _node = left;
        }
        else//右树是空的
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent -> _right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self& operator--()
    {
        if (_node->_left)//如果有左子树,下一个访问的就是左子树中的，找左子树中的最右结点
        {
            Node* left = _node->_left;
            while (left->_right)
            {
                left = left->_right;
            }
            _node = left;
        }
        else {//没有左子树，说明这一串子树都访问完了，需要往上找
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left  )
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
};

#pragma once
#include "Map.h"
#include "Set.h"
#include"RBTree.h"
#include<stdlib.h>
#include<time.h>

int main()
{
    Y::map<int, int> m;
    m.insert(std::make_pair(1,1));
    
    Y::set<int > s;
    
    srand(time(0));
    int total = 10;
    for (int i = 0; i < total; i++)
    {
        s.insert(rand());
    }
  
    cout << s.CheckBlance() << endl;


    Y::set<int>::iterator sit = s.begin();
    
    while ( sit != s.end()  )
    {
        cout << (*sit) << " ";
        ++sit;
    }
    cout << endl;

    Y::set<int>::reverse_iterator  rs = s.rbegin();
    
    while (rs != s.rend())
    {
        cout << (*rs) << " ";
        --rs;
    }
}

反向迭代器的实现(迭代器适配器)

上述对于反向迭代器的使用是用--来处理的，但是我们在stl中使用反向迭代器的时候是使用++的。

对于自定义类型的反向迭代器，可以直接适配。而vector和string的内置类型反向迭代器需要类型萃取。

可以实现一个由正向迭代器适配的反向迭代器

#pragma once
//使用正向迭代器来创造反向迭代器,类似适配器模式
//类型萃取之类的太过复杂暂时不实现
//反向迭代器适配器
template<class Iterator>
struct ReverseIterator
{
    typedef typename Iterator::reference Ref;//只要模板里面去取就用typename
    typedef typename Iterator::pointer Ptr;
    typedef ReverseIterator < Iterator > Self;
    Iterator _it;

    ReverseIterator(Iterator it)
        :_it(it)
    {}

    Ref operator*()
    {
        return *_it;
    }

    Ref operator->()
    {
        return _it.operator->();
    }

    Self& operator++()
    {
        --_it;
        return *this;
    }
    Self& operator--()
    {
        ++_it;
        return *this;
    }

    bool operator!=(const Self& s) const
    {
        return _it != s._it;
    }

    bool operator==(const Self& s)const
    {
        return _it == s._it;
    }

};

operator[]的访问

map.h

pair<iterator,bool> insert(const pair<const K, V>& kv)
{ 
    return _t.Insert(kv); 
}
V& operator[](const K& key)
{
    pair<iterator, bool > ret = insert(make_pair(key, V()));
    return ret.first->second;
}

RBTree.h

第7行，第25行，第111行。

pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root -> _col= BLACK;
            return make_pair(iterator(_root), true);
        }
        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if ( kot( cur->_data ) < kot(data) )//如果实现的是multimap这里使用的是<=
            {
                parent = cur;
                cur = cur->_right;
            }
            else if ( kot( cur->_data ) > kot(data) )
            {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return make_pair(iterator(cur), false);
            }
        }
        Node* newnode = new Node(data);
        newnode->_col = RED;
        if ( kot(parent->_data) < kot(data) )
        {
            parent->_right = newnode;
            newnode->_parent = parent;
        }
        else {
            parent->_left = newnode;
            newnode->_parent = parent;
        }
        cur = newnode;

        //如果父亲存在，且颜色为红色，则需要处理
        while (parent && parent->_col == RED)
        {
            //关键看叔叔
            Node* grandfather = parent->_parent; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红

            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //情况一：uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else { //情况 2+3  uncle不存在/uncle存在且为黑
                    if (cur == parent->_left) // 情况2: 单旋
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else { //情况三:双旋
                        RotateL(parent);
                        RotateR(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完就整棵树变成红黑树了
                }
            }
            else// parent == grandfather -> _right;
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)//情况一:叔叔存在且为红
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else {//情况二+三:叔叔存在且为黑或者不存在
                    if (cur == parent->_right)//情况二:单旋+变色
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完必定搞定
                }
            }
        }

        _root->_col = BLACK;
        return make_pair(iterator(newnode), true);
    }

代码

RBTree.h

#pragma once
#include <iostream>
#include"iterator.h"
using namespace std;
enum Color
{
    RED,
    BLACK
};
template<class T>
struct RBTreeNode
{
    RBTreeNode(const T& x)
        :_left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _data(x),
        _col(RED)
    {}

    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;

    T _data;
    Color _col;
};

template<class T, class Ref, class Ptr >
struct __TreeIterator
{
    typedef Ref reference;
    typedef Ptr pointer;
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator < T, Ref, Ptr > Self;

    Node* _node;
    __TreeIterator(Node* node)
        :_node(node)
    {}
    Ref operator*()
    {
        return _node->_data;//对于set是key,对于map是pair。T类型
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

    bool operator != (const Self& s) const
    {
        return _node != s._node;
    }
    bool operator == (const Self& s) const
    {
        return _node == s._node;
    }
    //重点
    Self& operator++()   //对于list来说,node=node->_next;
    {
        if (_node->_right)
        {
            //下一个访问的就是右树中，中序的第一个结点(最左)
            Node* left = _node->_right;
            while (left->_left)
            {
                left = left->_left;
            }

            _node = left;
        }
        else//右树是空的
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent -> _right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self& operator--()
    {
        if (_node->_left)//如果有左子树,下一个访问的就是左子树中的，找左子树中的最右结点
        {
            Node* left = _node->_left;
            while (left->_right)
            {
                left = left->_right;
            }
            _node = left;
        }
        else {//没有左子树，说明这一串子树都访问完了，需要往上找
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && parent->_right != cur)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
};

//KeyOfT——仿函数，若T为pair，用于取出T中的first(key)
template<class K, class T , class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef __TreeIterator < T, T&, T* > iterator;
    typedef __TreeIterator < T, const T&, const T* > const_iterator;

    typedef ReverseIterator<iterator> reverse_iterator;

    reverse_iterator rbegin()
    {
        Node* right = _root;
        while (right && right->_right)
        {
            right = right->_right;
        }
        return reverse_iterator(iterator(right));
    }

    reverse_iterator rend()
    {
        return reverse_iterator(iterator(nullptr));
    }

    iterator begin()
    {
        Node* left = _root;
        while (left && left->_left)
        {
            left = left->_left;
        }
        return iterator(left);
    }

    iterator end()
    {
        return iterator(nullptr);
    }

   
    RBTree()
        :_root(nullptr)
    {	}
    void Destroy(Node* root)
    {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    ~RBTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
    //拷贝构造和operator[]赋值

    Node* Find(const K& key)
    {
        KeyOfT kot;
        Node* cur = _root;
        while (cur)
        {
            if ( kot(cur->_data) > key)
            {
                cur = cur->_left;
            }
            else if ( kot(cur->_data) < key)
            {
                cur = cur->_right;
            }
            else {
                return cur;
            }
        }
        return nullptr;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;
        subL->_right = parent;

        Node* grandParent = parent->_parent;

        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else {
            if (grandParent->_left == parent)
            {
                grandParent->_left = subL;
            }
            else {
                grandParent->_right = subL;
            }
            subL->_parent = grandParent;
        }
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL ) {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* grandparent = parent->_parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else {
            if (grandparent->_left == parent)
            {
                grandparent->_left = subR;
            }
            else {
                grandparent->_right = subR;
            }

            subR->_parent = grandparent;
        }

       
    }
    pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root -> _col= BLACK;
            return make_pair(iterator(_root), true);
        }
        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if ( kot( cur->_data ) < kot(data) )//如果实现的是multimap这里使用的是<=
            {
                parent = cur;
                cur = cur->_right;
            }
            else if ( kot( cur->_data ) > kot(data) )
            {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return make_pair(iterator(cur), false);
            }
        }
        Node* newnode = new Node(data);
        newnode->_col = RED;
        if ( kot(parent->_data) < kot(data) )
        {
            parent->_right = newnode;
            newnode->_parent = parent;
        }
        else {
            parent->_left = newnode;
            newnode->_parent = parent;
        }
        cur = newnode;

        //如果父亲存在，且颜色为红色，则需要处理
        while (parent && parent->_col == RED)
        {
            //关键看叔叔
            Node* grandfather = parent->_parent; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红

            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //情况一：uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else { //情况 2+3  uncle不存在/uncle存在且为黑
                    if (cur == parent->_left) // 情况2: 单旋
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else { //情况三:双旋
                        RotateL(parent);
                        RotateR(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完就整棵树变成红黑树了
                }
            }
            else// parent == grandfather -> _right;
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)//情况一:叔叔存在且为红
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else {//情况二+三:叔叔存在且为黑或者不存在
                    if (cur == parent->_right)//情况二:单旋+变色
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转完必定搞定
                }
            }
        }

        _root->_col = BLACK;
        return make_pair(iterator(newnode), true);
    }


    bool _CheckBlance(Node* root, int blackNum, int count)
    {
        if (root == nullptr)
        {
            if (count != blackNum)
            {
                cout << "黑色节点的数量不相等" << endl;
                return false;
            }

            return true;
        }

        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "存在连续的红色节点" << endl;
            return false;
        }

        if (root->_col == BLACK)
        {
            count++;
        }

        return _CheckBlance(root->_left, blackNum, count)
            && _CheckBlance(root->_right, blackNum, count);
    }

    bool CheckBlance()
    {
        if (_root == nullptr)
        {
            return true;
        }

        if (_root->_col == RED)
        {
            cout << "根节点是红色的" << endl;
            return false;
        }

        // 找最左路径做黑色节点数量参考值
        int blackNum = 0;
        Node* left = _root;
        while (left)
        {
            if (left->_col == BLACK)
            {
                blackNum++;
            }

            left = left->_left;
        }

        int count = 0;
        return _CheckBlance(_root, blackNum, count);
    }
private:
    Node* _root;
};

Map.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K, class V>
    class map
    {
        //定义内部类
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename RBTree< K, pair< const K, V > , MapKeyOfT>::iterator iterator;
        typedef typename RBTree< K, pair< const K, V > , MapKeyOfT>::reverse_iterator reverse_iterator;
        
        reverse_iterator rbegin()
        {
            return _t.rbegin();
        }

        reverse_iterator rend()
        {
            return _t.rend();
        }

        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }

        pair<iterator,bool> insert(const pair<const K, V>& kv)
        { 
            return _t.Insert(kv); 
        }

        V& operator[](const K& key)
        {
            pair<iterator, bool > ret = insert(make_pair(key, V()));
            return ret.first->second;
        }
    private:
        RBTree< K, pair<const K, V>, MapKeyOfT > _t;
    };
}

Set.h

#pragma once
#include"RBTree.h"

namespace Y
{
    template< class K>
    class set
    {
        //定义内部类
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:

        //平时使用class和typename是一样的，但是这里是不一样的,取的是类模板的类型
        //因为我们先实例化的是set<int>,编译器走到这里的时候 RBTree< K, K, SetKeyOfT >还没被实例化出来，找不到这个类，typename告诉编译器后面等RBTree<>类模板实例化之后再去对应的实例化的类中去找
        typedef  typename RBTree< K, K, SetKeyOfT >::iterator iterator;
        typedef  typename RBTree< K, K, SetKeyOfT >::reverse_iterator reverse_iterator;

        reverse_iterator rbegin()
        {
            return _t.rbegin();
        }
        reverse_iterator rend()
        {
            return _t.rend();
        }

        iterator begin()
        {
            return _t.begin();
        }

        iterator end()
        {
            return _t.end();
        }

        pair<iterator,bool> insert(const K& k)
        {
            return _t.Insert(k);
        }
        bool CheckBlance()
        {
            return _t.CheckBlance();
        }
    private:
        RBTree< K, K , SetKeyOfT> _t;
    };
}

iterator.h

#pragma once
//使用正向迭代器来创造反向迭代器,类似适配器模式
//类型萃取之类的太过复杂暂时不实现
//反向迭代器适配器
template<class Iterator>
struct ReverseIterator
{
    typedef typename Iterator::reference Ref;//只要模板里面去取就用typename
    typedef typename Iterator::pointer Ptr;
    typedef ReverseIterator < Iterator > Self;
    Iterator _it;

    ReverseIterator(Iterator it)
        :_it(it)
    {}

    Ref operator*()
    {
        return *_it;
    }

    Ref operator->()
    {
        return _it.operator->();
    }

    Self& operator++()
    {
        --_it;
        return *this;
    }
    Self& operator--()
    {
        ++_it;
        return *this;
    }

    bool operator!=(const Self& s) const
    {
        return _it != s._it;
    }

    bool operator==(const Self& s)const
    {
        return _it == s._it;
    }

};

main.cpp

#pragma once
#include "Map.h"
#include "Set.h"
#include"RBTree.h"
#include<stdlib.h>
#include<string>
#include<time.h>


int main()
{

    Y::map<int, int> m;
    m.insert(std::make_pair(1, 1));
    m.insert(std::make_pair(4, 4));
    m.insert(std::make_pair(3, 3));
    m.insert(std::make_pair(2, 2));

    Y::map<int, int>::iterator it = m.begin();
    
    while (it != m.end())
    {
        cout << (*it).first << " " << (*it).second << endl;
        cout << it->first << " " << it->second << endl;
        ++it;
    }

    Y::map<int, int>::reverse_iterator rrit = m.rbegin();

    while (rrit != m.rend())
    {
        cout << rrit._it->first << " " << rrit._it->second << endl;
        ++rrit;
    }

    Y::set<int> s;
    
    srand(time(0));
    int total = 10;
    for (int i = 0; i < total; i++)
    {
        s.insert(rand());
    }
  
    cout << s.CheckBlance() << endl;


    Y::set<int>::iterator sit = s.begin();
    
    while ( sit != s.end()  )
    {
        cout << (*sit) << " ";
        ++sit;
    }
    cout << endl;

    Y::set<int>::reverse_iterator  rsit = s.rbegin();
    
    while (rsit != s.rend())
    {
        cout << (*rsit) << " ";
        ++rsit;
    }cout << endl;


    Y::map<string, string> dict;
    dict["sort"] ;
    dict["left"] = "左边";
    dict["left"] = "剩余";

    for (auto& e : dict)
    {
        cout << e.first << " " << e.second << endl;
    }
    dict["sort"] = "排序";
    for (auto& e : dict)
    {
        cout << e.first << " " << e.second << endl;
    }
}