map和set

关联式容器

键值对

set的简介

map的简介

AVL树的实现

红黑树的实现

红黑树封装map和set

全部代码

关联式容器

关联式容器也是用来存储数据的，与序列式容器vector，list等等不同的是，它存储的是<Key,Value>的键值对，在数据检索时效率更高

STL中分为两种，一种是树形结构，另一种则是哈希结构

树型结构的关联式容器主要有四种：map、set、multimap、multiset，底层结构都是平衡搜索树(红黑树)

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息，比如字典中的一个单词，则有与它相应的中文意思，单词可为键值Key，中文意思则为Value

set的简介

set具有排序+去重的作用，而multiset则只有排序的作用

set中的元素的key即是value，即set只存放value，其底层存放的是<value,value>

set中的元素不能在容器中修改(元素总是const)，但可以插入或者删除

在multiset容器中，用find函数查找的val有多个值时，返回中序第一个val值所在节点的迭代器

set中插入元素时，只需要插入value即可，不需要构造键值对

map的简介

map具有排序+去重的作用，而multimap则只有排序的作用，所以map中的key是唯一的，multimap中的key是可以重复的

map中存放的元素都是<key,value>键值对

在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair

在内部，map中的元素总是按照键值key进行比较排序的

map支持下标访问符，即在[]中放入key，就可以找到与key对应的value

AVL树的实现

AVL树的左右子树都是AVL树，它的左右子树高度差的绝对值不超过1，所以它也是高度平衡的，如果它有n个结点，其高度可保持在 log2 n，搜索时间复杂度O( log2 n)

由于AVL树比较复杂，而且一般工作中不需要去实现，库里面有，所以只讲插入，简单了解它即可

节点结构

这里采用非递归的写法，以及三叉链的形式，借助平衡因子来维持平衡

AVL树的私有成员及其构造函数，以及依然采用模板，泛型写法

开始是空树时

其余情况，先按照二叉搜索树的形式插入

每次插入时调节每个节点的平衡因子

当其中一个节点的平衡因子为2或-2时，则需要旋转来控制平衡

由于实体图情况种类太多，所以采用抽象图的方法则只有4种旋转

右单旋

上述情况是要旋转的节点是根节点，所以最后代码如下图

如果不是根节点则要些微改变，代码如下

**左单旋 **

上述情况是要旋转的节点是根节点，所以最后代码如下图

如果不是根节点则要些微改变，代码如下

左右双旋

这里左右双旋只调用左旋转和右旋转还不行，还需单独调整它的平衡因子，因为左单旋或者右单选调节的平衡因子，在左右双旋不一定正确

如何调整正确每个节点的平衡因子，主要看上图中第二个图形subLR的平衡因子，所以先保存其平衡因子

然后就有下列几种情况，走到else则表示前面的插入早就出问题了

右左双旋

这里右左双旋只调用右旋转和左旋转还不行，还需单独调整它的平衡因子，因为右单旋或者左单选调节的平衡因子，在右左双旋不一定正确

如何调整正确每个节点的平衡因子，主要看上图中第二个图形subRL的平衡因子，所以先保存其平衡因子

然后就有下列几种情况，走到else则表示前面的插入早就出问题了

验证是否是AVL树

一个是检验它是否是二叉搜索树，另一个则是检验它是否平衡，验证它是二叉搜索树，只需要写出它的中序遍历，看其是否有序即可

检验AVL树是否平衡

首先如果这颗树为空树就直接返回true

通过每个节点左右子树的高度来检查，首先先算出高度

然后通过该节点左右子树的高度差的绝对值与平衡因子的比较，来确定是否平衡，不平衡就返回false

最后就是层层递归下去，把每个节点都遍历一遍，看是否符合平衡

AVL树的性能

查询时，效率非常高，时间复杂度为log2 n，但要对AVL树做一些结构修改的操作，性能非常低，比如：插入时要维护平衡，旋转的次数就会非常多，所以工作中用红黑树用的比较多

红黑树的实现

概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black，所以这里可以用到枚举

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，是接近平衡的，性质决定的

性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)，所以一条路径走完是走到nullptr才结束

首先定义一个枚举类型，来确定节点颜色

其次则是定义一个结构体类型，来封装节点

然后采用类模板的方式来封装类

和AVL树一样，红黑树也比较复杂，库里面有，所以只写插入，简单了解其过程即可

首先如果是一颗空树，则直接插入节点，节点颜色定为黑色

然后其余情况则是先按照二叉搜索树的插入过程插入节点，插入红节点比插入黑节点更便于后面维持平衡时修改红黑树结构，所以初始时插入红节点

父亲节点存在且为红，主要是看叔叔节点来控制平衡

如果父亲节点是爷爷节点的左节点，分几种情况来讨论

叔叔节点存在且为红

将父亲节点和叔叔节点都变黑，然后将祖父节点变红，如果祖父节点不是根节点，则还需继续向上调整，出循环后，将根节点变黑即可

叔叔节点不存在或者为黑时，只变色无法维持平衡了，那么则需通过旋转来维持平衡

不存在时

右单旋，然后将祖父节点变红，父亲节点变黑即可

存在且为黑时

先向上调整颜色，然后右单旋，最后将父亲节点变黑，祖父节点变红即可

上述两种其实算是一种情况，所以代码如上图所示

不存在，且新增节点是父亲节点的右孩子时

先左单旋，然后右单旋，最后将新增节点变黑，祖父节点变红即可

存在且为黑，且cur是其父亲节点的右孩子时

先向上调整变色，然后先左单旋，然后右单选，最后将cur节点变黑，祖父节点变红即可

上述两种情况其实算一种情况，所以代码如上图所示

如果父亲节点是爷爷节点的右节点，也分几种情况来讨论

叔叔节点存在且为红

将父亲节点和叔叔节点都变黑，然后将祖父节点变红，如果祖父节点不是根节点，则还需继续向上调整，出循环后，将根节点变黑即可

叔叔节点不存在或者为黑时，只变色无法维持平衡了，那么则需通过旋转来维持平衡

不存在时

左单旋，然后将祖父节点变红，父亲节点变黑即可

存在且为黑时

先向上调整颜色，然后左单旋，最后将父亲节点变黑，祖父节点变红即可

上述两种其实算是一种情况，所以代码如上图所示

不存在，且新增节点是父亲节点的左孩子时

先右单旋，然后左单旋，最后将新增节点变黑，祖父节点变红即可

存在且为黑，且cur是其父亲节点的左孩子时

先向上调整变色，然后先左单旋，然后右单选，最后将cur节点变黑，祖父节点变红即可

上述两种情况其实算一种情况，所以代码如上图所示

如果父亲节点是爷爷节点的右节点，也分几种情况来讨论

注意：上述红黑树的旋转函数，只需将AVL树的左旋转和右旋转拷贝过来，然后把调整平衡因子的语句删掉即可

检验是否是红黑树

一个是检验它是否是二叉搜索树，另外则是判读是否符合红黑树的性质

检验是否是二叉搜索树只需写一个中序遍历，看是否有序即可

检验是否符合红黑树的性质

检验第二条性质，第一条和第五条都无需检验了

检验第三条性质

判断它的两个孩子比较难处理，可以转换为检验它的父亲节点的颜色，只要它和它父亲节点颜色一致，则不满足第三条性质

** 检验第四条性质**

首先需算出其中一条路径的黑色节点个数，然后以此为基准，判断其它路径的黑色节点与此路径的黑色节点个数是否相等即可，这里以最左路径为基准，然后将最左路径的黑色节点个数作为参数传给子函数，同时定义了blackNum，来统计黑色节点个数，作为子函数的形参

这里要采用二叉数的深度遍历，来统计每一条路径的黑色节点个数，当走完一条路径后，然后用它与最左路径的黑色节点个数作比较，相等则符合第四条性质，不相等则不符合

注意：上述的blackNum一定不能传引用给子函数，只能作其的形参才能验证此性质

红黑树封装map和set

因为一棵红黑树要同时封装map和set，所以红黑树的节点封装有些变化，如下图

*同时还需要写一个迭代器，T对应是T，Ref对应是T&，Ptr对应是T **

对*运算符的重载，主要是为了应用于set中，得到set中存的数据

对->运算符的重载，主要是为了应用于map中，因为map中存的是pair，所以返回的pair的地址，本来要得到pair中的first或者second需要两个->，因为编译器优化了，所以解引用时只需要一个->即可

判断两个节点相不相等，比较它们两个的地址即可

重载++运算符

其实就是按中序遍历的路径走

** 重载--运算符**

上述++和--运算符的重载，其实思路是一致的

因为map和set存储的数据不一样，所以在红黑树的模板参数中多加了一个仿函数的模板参数

同时有const迭代器和普通迭代器

初始节点应该是红黑树的最左节点，而结尾是最右节点，也就是nullptr结尾的，所以结尾以nullptr结束

拷贝构造

如果开始是一颗空树，则直接返回nullptr即可，否则则先拷贝它的根节点，及其保持颜色一致，然后再左右分别递归下去，然后则是子节点与父亲节点的连接，最后返回根节点即可

赋值运算符重载

首先是实参传给形参的时候，会拷贝构造出一颗树，然后直接将其构造的树的根节点与待要被赋值的树的根节点作交换即可

析构函数

首先对红黑树进行一次遍历，将其节点全部销毁，最后再将根节点置为nullptr即可

首先map有两个模板参数，key和value

其余的像begin()，end()，insert()等等直接复用即可

重载[]运算符

[]有修改value或者是插入元素pair的作用

全部代码

//AVL

#pragma once

template<class K,class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    pair<K, V> _kv;

    int _bf; //balance factor

    AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv)
    {}
};

template<class K ,class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    AVLTree():_root(nullptr)
    {}

    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

        //控制平衡
        //1.更新平衡因子 -- 新增节点到根节点的祖先路径
        //2.出现异常平衡因子，那么需要旋转平衡处理
        while (parent)
        {
            if (cur == parent->_left)
                parent->_bf--;
            else
                parent->_bf++;

            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                //继续往上更新
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //旋转处理
                //右单旋
                if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                //左单旋
                else if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                else
                {
                    assert(false);
                }
                break;
            }
            else
            {
                //说明插入更新平衡因子之前，树中平衡因子就有问题了
                assert(false);
            }
        }
        return true;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        Node* parentParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;

        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
        subR->_bf = parent->_bf = 0;
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        Node* parentParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (_root == parent)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subL;
            }
            else
            {
                parentParent->_right = subL;
            }
            subL->_parent = parentParent;
        }
        subL->_bf = parent->_bf = 0;
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        if (bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else if (bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        if (bf == 1)
        {
            parent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
        else if (bf == 0)
        {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void InOrder()
    {
        _InOrder(_root);
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    bool IsBalance()
    {
        return _IsBalance(_root);
    }

    int Height(Node* root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    bool _IsBalance(Node* root)
    {
        if (root == nullptr)
        {
            return true;
        }

        //对当前树进行检查
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);

        if (rightHeight - leftHeight != root->_bf)
        {
            cout << root->_kv.first << "现在是:" << root->_bf << endl;
            cout << root->_kv.first << "现在是:" << rightHeight - leftHeight << endl;
            return false;
        }

        return abs(rightHeight - leftHeight) < 2
            && _IsBalance(root->_left)
            && _IsBalance(root->_right);
    }
private:
    Node* _root;
};

void TestAVLTree()
{
    AVLTree<int, int> t;
    //int a[] = { 5,4,3,2,1,0 };
    //int a[] = { 16,3,7,11,9,26,18,14,15 };
    int a[] = { 4,2,6,1,3,5,15,7,16,14 };
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));
        cout << "Insert" << e << ":" << t.IsBalance() << endl;
    }
    t.InOrder();
    cout << t.IsBalance() << endl;
}

//红黑树-副本

#pragma once

#include<time.h>

enum Colour
{
    RED,
    BLACK
};

template<class K , class V>
struct RBTreeNode
{
    RBTreeNode<K,V>* _left;
    RBTreeNode<K,V>* _right;
    RBTreeNode<K,V>* _parent;
    pair<K, V> _kv;

    Colour _col;

    RBTreeNode(const pair<K,V>& kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
    {}
};

template<class K,class V>
struct RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    RBTree() :_root(nullptr)
    {}

    bool Insert(const pair<K,V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(kv);
        cur->_col = RED; //新增节点
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

        //控制平衡
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                //1.uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    //变色+继续向上处理
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else //2 + 3、uncle不存在/存在且为黑
                {
                    //       g
                    //    p
                    // c

                    //       g
                    //    p
                    //       c
                    if (cur == parent->_left)
                    {
                        //单旋
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    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)
                {
                    //变色+继续向上处理
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 2 + 3、uncle不存在/ 存在且为黑
                {
                    // g
                    //     p
                    //         c

                    //g
                    //    p
                    //c
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;
                }
            }
        }

        _root->_col = BLACK;

        return true;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        Node* parentParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;

        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        Node* parentParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (_root == parent)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subL;
            }
            else
            {
                parentParent->_right = subL;
            }
            subL->_parent = parentParent;
        }
    }

    void InOrder()
    {
        _InOrder(_root);
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    bool IsBalance()
    {
        if (_root && _root->_col == RED)
        {
            cout << "根节点不是黑色" << endl;
            return false;
        }

        //最左路径黑色节点数量做基准值
        int banchmark = 0;
        Node* left = _root;
        while (left)
        {
            if (left->_col == BLACK)
                ++banchmark;

            left = left->_left;
        }
        int blackNum = 0;
        return _IsBalance(_root, banchmark, blackNum);
    }

    bool _IsBalance(Node* root,int banchmark,int blackNum)
    {
        if (root == nullptr)
        {
            if (banchmark != blackNum)
            {
                cout << "存在路径黑色节点的数量不相等" << endl;
                return false;
            }
            return true;
        }

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

        if (root->_col == BLACK)
        {
            ++blackNum;
        }
        return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
    }

    int Height()
    {
        return _Height(_root);
    }

    int _Height(Node* root)
    {
        if (root == nullptr)
            return 0;
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    
private:
    Node* _root;
};

void TestRBTree()
{
    RBTree<int, int> t;
    vector<int> v;
    srand(time(0));
    int N = 10000;
    for (int i = 0; i < N; i++)
    {
        //v.push_back(rand());
        v.push_back(i);
    }
    //int a[] = { 5,4,3,2,1,0 };
    //int a[] = { 16,3,7,11,9,26,18,14,15 };
    //int a[] = { 4,2,6,1,3,5,15,7,16,14 };
    for (auto e : v)
    {
        t.Insert(make_pair(e, e));
        if (!t.IsBalance())
        {
            cout << "Insert" << e << endl;
        }
    }
    t.InOrder();
    //cout << t.IsBalance() << endl;
    cout << "高度:" << t.Height() << endl;
}

//改善后的红黑树
#pragma once
#include<time.h>

enum Colour
{
    RED,
    BLACK
};

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    T _data;

    Colour _col;

    RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_data(data)
    {}
};

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T, Ref, Ptr> Self;
    Node* _node;

    RBTreeIterator(Node* node):_node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

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

    Self& operator++()
    {
        if (_node->_right)
        {
            Node* min = _node->_right;
            while (min->_left)
            {
                min = min->_left;
            }

            _node = min;
        }
        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* max = _node->left;
            while (max->_right)
            {
                max = max->_right;
            }
            _node = max;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

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

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

};

//set  RBTree<K, K, SetKeyOfT>
//map  RBTree<K, pair<K,V>, MapKeyOfT>
template<class K,class T,class KeyOfT>
struct RBTree
{
    typedef RBTreeNode<T> Node;
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()
    {
        return iterator(nullptr);
    }

    RBTree():_root(nullptr)
    {}

    RBTree(const RBTree<K, T, KeyOfT>& t)
    {
        _root = Copy(t._root);
    }

    RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
    {
        swap(_root, t._root);
        return *this;
    }

    ~RBTree()
    {
        Destroy(_root);
        _root = nullptr;
    }

    iterator Find(const K& key)
    {
        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();
    }

    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))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kot(cur->_data) > kot(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(iterator(_root), false);
            }
        }

        cur = new Node(data);
        Node* newnode = cur;
        cur->_col = RED; //新增节点
        if (kot(parent->_data) < kot(data))
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

        //控制平衡
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                //1.uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    //变色+继续向上处理
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else //2 + 3、uncle不存在/存在且为黑
                {
                    //       g
                    //    p
                    // c

                    //       g
                    //    p
                    //       c
                    if (cur == parent->_left)
                    {
                        //单旋
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    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)
                {
                    //变色+继续向上处理
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 2 + 3、uncle不存在/ 存在且为黑
                {
                    // g
                    //     p
                    //         c

                    //g
                    //    p
                    //c
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;
                }
            }
        }

        _root->_col = BLACK;

        return make_pair(iterator(newnode), true);
    }
private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }

        Node* parentParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;

        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }

        Node* parentParent = parent->_parent;

        subL->_right = parent;
        parent->_parent = subL;

        if (_root == parent)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subL;
            }
            else
            {
                parentParent->_right = subL;
            }
            subL->_parent = parentParent;
        }
    }

    void Destroy(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete 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;

        if (newRoot->_right)
            newRoot->_right->_parent = newRoot;

        return newRoot;
    }
private:
    Node* _root;
};

//map

#pragma once
#include"RBTree.h"

namespace bit
{
    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);
        }

        iterator find(const K& key)
        {
            return _t.Find(key);
        }

        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;
    };

    void test_map()
    {
        map<string, string> dict;
        //dict.insert(make_pair("sort", "排序"));
        //dict.insert(make_pair("string", "字符串"));
        //dict.insert(make_pair("map", "地图"));
        //dict["left"];
        dict["left"] = "晚";
        //dict["map"] = "fsgd";

        auto it = dict.begin();
        while (it != dict.end())
        {
            cout << it->first << ":" << it->second << endl;
            ++it;
        }
        cout << endl;
    }
}

//set

#pragma once
#include"RBTree.h"

namespace bit
{
    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();
        }

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

        iterator find(const K& key)
        {
            return _t.Find(key);
        }
    private:
        RBTree<K, K, SetKeyOfT> _t;
    };

    void test_set()
    {
        set<int> s;
        s.insert(1);
        s.insert(4);
        s.insert(2);
        s.insert(24);
        s.insert(2);
        s.insert(12);
        s.insert(6);

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

        for (auto e : s)
        {
            cout << e << " ";
        }
        cout << endl;

        set<int> copy(s);
        for (auto e : copy)
        {
            cout << e << " ";
        }
        cout << endl;

        set<int> ss;
        ss.insert(111);
        ss.insert(422);

        copy = ss;
        for (auto e : copy)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}