map和set的实现

RBTree

红黑树修改版本

RBTreeNode树里面的每一个节点

#pragma once
#include <iostream>
using namespace std;

enum Color
{
    RED,
    BLACK
};
template <class T>//这里只有一个T变量，可以是一个key也可以是一个pair

struct RBTreeNode
{
    RBTreeNode<T> *_left;
    RBTreeNode<T> *_right;
    RBTreeNode<T> *_parent;
    T _data;//只使用T的data变量
    Color _col; //控制颜色
    RBTreeNode(const T &data)
        : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //一开始的颜色给红色
    {
    }
};

树的迭代器Iterator

template <class T, class Ref, class Ptr> // T是变量类型，Ref返回的是里面的值，Ptr返回的是里面的地址
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;//里面的存储的元素类型是T
    typedef RBTreeIterator<T,Ref, Ptr> Self;//迭代器进行重定义
    Node *_node;
    RBTreeIterator(Node *node)
        : _node(node)
    {
    }

    Ref operator*() //这个返回的是T&返回的是值
    {
        return _node->_data;
    }
    Ptr operator->()
    {
        return &_node->_data;
    }
    Self& operator++()//返回的是自己这个指针
    //中序遍历，从小到大
    {
        // 1. 左边都访问过了，假如右树存在，下一个就要访问右树的最左节点
        // 2. 如果右为空，我所在的子树完了，我是父亲的左边，下一个访问父亲
        // 2.1我是父亲的右边，访问的父亲的父亲

        if (_node->_right) //右不为空
        {
            Node *min = _node->_right; //找右的最左节点
            while (min->_left)
            {
                min = min->_left;
            }
            _node = min;
        }
        else
        {
            //右为空，找孩子是父亲左的祖先
            Node *cur = _node;
            Node* parent=cur->_parent;
            //如果cur是父亲的右
            while(parent&&cur==parent->_right)
            {
                cur=parent;
                parent=parent->_parent;
            }
            //cur是父亲的左
            _node=parent;
        }
        return  *this;
    }
    Self& operator--()
    {
        //右根左，和++反过来的
        //左不为空，到左节点的最右边
        //左为空，是父亲的右节点，到父亲
        //是父亲的左节点，到孩子是父亲的右节点
        if(_node->_left)
        {
            //左不为空，
            Node* max=_node->_left;
            while(max->_right)
            {
                max=max->_right;
            }
            _node=max;
        }
        else
        {
            Node* parent=_node->_parent;
            while(parent&&parent->_left==_node)
            {
                
                _node=parent;
                parent=parent->_parent;
            }
            _node=_node->_parent;

        }

        return *this;
    }

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

};

RBTree

// set传的T是key RBTree<K,K,SetKeyOfT>
// map传的T是pair  RBTree<K,pair<K,pair<K,V>,MapKeyOfT>

template <class K, class T, class KeyOfT> // KeyOfT是一个仿函数，我们要取出T的first
//K是为了获得T里面的第一个参数的类型
//T里面就是树里面存储的元素
//KeyOfT是获得出T里面第一个参数的值
class RBTree
{
    typedef RBTreeNode<T> Node;

private:
    Node *_root;

private:
    void _InOrder(Node *root)//中序遍历
    {
        if (root == nullptr)
            return;
        _InOrder(root->_left);
        cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }
    void RotateR(Node *parent)
    {
        //右单旋转
        Node *subL = parent->_left;           //子节点
        Node *subLR = subL->_right;           //子节点的右节点
        Node *parentparent = parent->_parent; //出问题节点的父节点
        parent->_left = subLR;
        subL->_right = parent;
        parent->_parent = subL;
        if (subLR)
            subLR->_parent = parent;

        //和父节点的父节点连接
        if (parent == _root)
        {
            //要旋转的节点已经是根
            //更新根
            _root = subL;
            _root->_parent = nullptr; //更新顶部
        }
        else
        {
            //父节点上面还有节点
            if (parentparent->_left == parent)
            {
                //是左节点
                subL->_parent = parentparent;
                parentparent->_left = subL;
            }
            else
            {
                subL->_parent = parentparent;
                parentparent->_right = subL;
            }
        }
    }
    void RotateL(Node *parent) //左单旋
    {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        Node *parentparent = parent->_parent;
        parent->_parent = subR;
        subR->_left = parent;
        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentparent->_right == parent)
            {
                parentparent->_right = subR;
                subR->_parent = parentparent;
            }
            else
            {
                parentparent->_left = subR;
                subR->_parent = parentparent;
            }
        }
    }

public:
    typedef RBTreeIterator<T, T &, T *> Iterator;
    typedef RBTreeIterator<T,const T&,const T*> const_Iterator;

    //中序遍历就是从小到大的
    Iterator begin() //因为它是走中序，所以第一个是最左节点,最小值
    {
        Node *min = _root; //最小值，就是左节点
        while (min && min->_left)
        {
            min = min->_left;
        }

        return Iterator(min);
    }
    Iterator end()
    {
        //最大值的下一个节点
        //最右边的下一个是null

        return Iterator(nullptr);
    }

    Iterator Find(const K& key)//K是为了取出V里面的第一个参数
    {
        Node* cur=_root;
        KeyOfT kot;//使用仿函数，调用
        while(cur)
        {
            if(kot(cur->_data)<key)
            {
                cur=cur->_right;
            }
            else if(kot(cur->_data)>key)
            {
                cur=cur->_left;
            }
            else
            {
                return Iterator(cur);
            }
        }
        return end();//没有找到，就返回end
    }

    RBTree()
        : _root(nullptr)
    {
    }
    ~RBTree()
    {
        Destroy(_root);
        _root=nullptr;
    }
    RBTree(const RBTree<K,T,KeyOfT>&t)
    {
        _root=Copy(t._root);
    }
    Node* Copy(Node* root)
    {
        if(root==nullptr)
        {
            return nullptr;
        }
        //前序遍历
        Node* newRoot=new Node(root->_data);
        newRoot->_col=root->_col;

        newRoot->_left=Copy(root->_left);
        newRoot->_right=Copy(root->_right);
        if(newRoot->_left)
        {
            newRoot->_left->_parent=newRoot;
        }
        else if(newRoot->_right)
        {
            newRoot->_right->_parent=newRoot;
        }


        return newRoot;
    }

    RBTree<K,T,KeyOfT>& operator=(RBTree<K,T,KeyOfT> t)
    {
        swap(_root,t._root);//这里的t是拷贝构造，所以这里的交换不会影响t
        return *this;

    }
    void Destroy(Node* root)
    {
        if(root==nullptr)
        {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;//后序遍历

    }
    pair<Iterator,bool> Insert(const T &data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(Iterator(_root),true);
        }
        //

        //因为我们需要知道它的T的参数是什么
        //这里我们添加一个
        KeyOfT kot; //使用这个来进行比较,仿函数

        Node *cur = _root;
        Node *parent = nullptr; //还要找到父亲
        while (cur)
        {
            if (kot(cur->_data) > kot(data)) //这里如果是pair，我们就得按照k去比较大小,所以这里我们需要知道它是key还是pair
            {
                //取出它的有效比较对象来进行比较
                parent = cur;
                cur = cur->_left;
            }
            else if (kot(cur->_data) < kot(data)) //比他大，在右边
            {
                //只要把key取出来就都可以使用这个东西
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return make_pair(Iterator(cur),false);//这个值存在，就返回这个已近有的节点
            }
        }
        //走到这里，就可以链接上
        cur = new Node(data);

        Node* newnode=cur;//把这个新节点给保持起来
        cur->_col = RED; //新增节点颜色给红色

        cur->_parent = parent;              //链接上父亲
        if (kot(parent->_data) > kot(data)) //父亲的值也能取出来
        {
            //比他小，在左边
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        //插入之前一定是红黑树
        //这里就要控制平衡，通过颜色
        //插入黑节点（影响路径），还是红节点（只影响自己的，不影响其他区域）

        //往上调整
        //我为红，父亲如果为红，爷爷一定是黑色
        // 1.叔叔存在且为红
        while (parent && parent->_col == RED) //往上处理,父亲颜色为红色，就要处理，黑色就不要处理,为红，就不是根
        {
            Node *grandparent = parent->_parent;
            if (parent == grandparent->_left)
            {
                Node *uncle = grandparent->_right; //叔叔就是在右边
                //叔叔存在且为红
                if (uncle && uncle->_col == RED)
                {
                    //叔叔存在，且为红
                    //变色，继续向上处理
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandparent->_col = RED;

                    cur = grandparent; //继续迭代往上操作
                    parent = cur->_parent;
                }

                //叔叔不存在
                else //不存在，或存在且为黑
                {
                    //不存在,进行旋转
                    //旋转+变色
                    if (cur == parent->_left)
                    {
                        RotateR(grandparent); //进行右单旋转
                        //变色
                        parent->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    else
                    {
                        //双旋
                        //左右双旋
                        // p进行右单旋，g左单旋，g变红藕，cur变黑，
                        RotateL(parent);
                        RotateR(grandparent);
                        cur->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    break;
                }
            }
            else //父亲是祖父的右边
            {
                Node *uncle = grandparent->_left; //叔叔就是在右边
                //叔叔存在且为红
                if (uncle && uncle->_col == RED)
                {
                    //叔叔存在，且为红
                    //变色，继续向上处理
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandparent->_col = RED;

                    cur = grandparent; //继续迭代往上操作
                    parent = cur->_parent;
                }

                //叔叔不存在
                else //不存在，或存在且为黑
                {
                    //不存在,进行旋转
                    //旋转+变色
                    if (cur == parent->_right)
                    {
                        RotateL(grandparent); //进行右单旋转
                        //变色
                        parent->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandparent);
                        cur->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK; //根的一定是黑色

        return make_pair(Iterator(newnode),true);
    }
};

map

#pragma once
#include "RBtree.hpp"

namespace xzw
{
    template <class K, class V>
    class map
    {

    public:
        struct MapKeyOfT //仿函数,泛型编程，复用同一棵树
        {
            const K &operator()(const pair<K, V> &kv)
            {
                return kv.first; //返回的是第一个参数
            }
        };

        typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator Iterator;//对于一个类型的使用，我们就要声明，不然编译器以为是一个变量

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

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


        V& operator[](const K&key)
        {   
            auto ret=_t.Insert(make_pair(key,V()));
            return ret.first->second;
        }
    private:
        RBTree<K, pair<K, V>, MapKeyOfT> _t; //用第二个模板参数来控制
    };

};

set

#pragma once
#include "RBtree.hpp"

namespace xzw
{
    template <class K>
    class set
    {

    public:
        struct SetKeyOfT //仿函数
        {
            const K &operator()(const K &k)
            {
                return k; //返回的是第一个参数
            }
        };
        typedef typename RBTree<K, K, SetKeyOfT>::Iterator Iterator; //取出它的内嵌类型，再进行重命名

        Iterator begin()
        {
            return _t.begin();
        }
        Iterator end()
        {
            return _t.end();
        }
        Iterator Find(const K& key)
        {
            return _t.Find(key);
        }
        pair<Iterator,bool> insert(const K &key)
        {
            return _t.Insert(key);
        }


    private:
        RBTree<K, K, SetKeyOfT> _t; //用第二个模板参数来控制
    };

};