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

enum Color
{
    RED,
    BLACK
};

template<class T>
class treenode
{
public:
    treenode<T>* _left;
    treenode<T>* _right;
    treenode<T>* _parents;
    enum Color _col;
    T _data;

    //构造函数
    treenode(const T& data)
        :_left(nullptr)
        , _right(nullptr)
        , _parents(nullptr)
        , _col(RED)
        , _data(data)
    {}
};

template<class T,class ref,class ptr>
struct treeiterator
{
    typedef treenode<T> Node;
    typedef treeiterator<T, ref, ptr> self;
    Node* _node;
    //构造函数
    treeiterator(Node* node)
        :_node(node)
    {}
    treeiterator(treeiterator<T, const ref, const ptr>& it)
    {
        _node = it._node;
    }


    ref operator*()
    {
        return _node->_data;
    }
    ptr operator->()
    {
        return &(_node->_data);
    }
    self& operator++()
    {
        if (_node->_right != nullptr)
        {
            //右子树的最左节点
            Node* cur = _node->_right;
            while (cur->_left)
            {
                cur = cur->_left;
            }
            _node = cur;
        }
        else
        {
            //找父亲的孩子是左节点，此时这个父亲节点就是所需要的节点
            Node* parents = _node->_parents;
            while (parents && parents->_right == _node)
            {
                _node = parents;
                parents = parents->_parents;
            }
            _node = parents;
        }
        return *this;
    }
    self& operator--()
    {
        if (_node->_left)
        {
            //左子树的最右节点
            Node* cur = _node->_left;
            while (cur->_right)
            {
                cur = cur->_right;
            }
            _node = cur;
        }
        else
        {
            Node* parents = _node->_parents;
            //找孩子是父亲的右节点，此时这个父亲节点就是所需要的节点
            while (parents && parents->_left == _node)
            {
                _node = parents;
                parents = parents->_parents;
            }
            _node = parents;
        }
        return *this;
    }
    bool operator!=(const self& s)
    {
        return _node != s._node;
    }
    bool operator==(const self& s)
    {
        return _node == s._node;
    }
};

template<class k, class T,class type>
class RBtree
{
public:
    RBtree() = default;
    typedef treeiterator<T, T&, T*> iterator;
    typedef treeiterator<T, const T&, const T*> const_iterator;



    iterator begin()
    {
        treenode<T>* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }
        return iterator(cur);
    }
    iterator end()
    {
        return iterator(nullptr);
    }
    const_iterator begin()const
    {
        treenode<T>* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }
        return const_iterator(cur);
    }
    const_iterator end()const
    {
        return const_iterator(nullptr);
    }

    pair<iterator,bool> insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new treenode<T>(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), true);
        }
        else
        {
            treenode<T>* parents = nullptr;
            treenode<T>* cur = _root;
            type tn;
            while (cur)
            {
                if (tn(cur->_data) > tn(data))
                {
                    parents = cur;
                    cur = cur->_left;
                }
                else if (tn(cur->_data) < tn(data))
                {
                    parents = cur;
                    cur = cur->_right;
                }
                else
                {
                    break;
                }
            }
            //此时cur就是要新插入的节点的位置
            if (cur != nullptr)
            {
                //cout << "插入失败，该节点已存在" << endl;
                return make_pair(iterator(cur),false);
            }
            //走到这里表示cur为空，树中没有kv这个值
            cur = new treenode<T>(data);
            treenode<T>* node = cur;
            if (tn(parents->_data) > tn(data))
            {
                parents->_left = cur;
                cur->_parents = parents;
            }
            else
            {
                parents->_right = cur;
                cur->_parents = parents;
            }
            while (parents && parents->_col == RED)
            {
                treenode<T>* grandfather = parents->_parents;
                if (parents == grandfather->_right)
                {
                    //g为黑，c为红,p为红
                    treenode<T>* uncle = grandfather->_left;
                    if (uncle && uncle->_col == RED)
                    {
                        //变色处理
                        parents->_col = BLACK;
                        grandfather->_col = RED;
                        uncle->_col = BLACK;

                        //还需继续向上调整
                        cur = grandfather;
                        parents = cur->_parents;
                    }
                    else
                    {
                        //此时uncle不存在或uncle为黑色节点
                        if (parents->_right == cur)
                        {
                            rotateL(grandfather);
                            parents->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else//parents->_left == cur
                        {
                            rotateR(parents);
                            rotateL(grandfather);
                            grandfather->_col = RED;
                            cur->_col = BLACK;
                        }
                        break;
                    }
                }
                else//parents == grandfather->_left
                {
                    treenode<T>* uncle = grandfather->_right;
                    //g为黑，c为红,p为红
                    if (uncle && uncle->_col == RED)
                    {
                        //变色处理
                        parents->_col = BLACK;
                        grandfather->_col = RED;
                        uncle->_col = BLACK;

                        //还需继续向上调整
                        cur = grandfather;
                        parents = cur->_parents;
                    }
                    else
                    {
                        //此时uncle不存在或uncle为黑色，这两种情况所进行的处理是一样的
                        if (parents->_left == cur)
                        {
                            rotateR(grandfather);
                            parents->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            //执行右旋
                            rotateL(parents);
                            rotateR(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
            }
            _root->_col = BLACK;
            return make_pair(node,true);
        }
    }

    bool checktree_is_red_black(treenode<T>* root, int black_path_size, int blacksize)
    {
        if (root == nullptr)
        {
            if (blacksize == black_path_size)
                return true;
            else
                return false;
        }
        treenode<T>* parents = root->_parents;
        if (parents && root->_col == RED && parents->_col == RED)
        {
            return false;
        }
        if (root->_col == BLACK)
            ++black_path_size;

        return checktree_is_red_black(root->_left, black_path_size, blacksize) && checktree_is_red_black(root->_right, black_path_size, blacksize);
    }
    //红黑树删除
    size_t  erase(const k& key)
    {
        //删除，使用替代法与前面的二叉树一致
        //删除的节点左为空
        
        //首先找到该节点
        treenode<T>* parents = nullptr;
        treenode<T>* cur = _root;
        type ty;
        while (cur)
        {
            if (ty(cur->_data) > key)
            {
                parents = cur;
                cur=cur->_left;
            }
            else if(ty(cur->_data) < key)
            {
                parents = cur;
                cur = cur->_right;
            }
            else
            {
                break;
            }
        }
        if (cur == nullptr)
        {
            cout << "要删除的值不存在" << endl;
            return 0;
        }
        if (cur->_left == nullptr)
        {
            //此节点为根节点
            if (parents==nullptr)
            {
                _root = _root->_right;
                if(_root)
                    _root->_parents = nullptr;
            }
            //不为根节点
            else
            {
                if (parents->_left == cur)
                {
                    parents->_left = cur->_right;
                    if (cur->_right)
                        cur->_right->_parents = parents;
                }
                else
                {
                    parents->_right = cur->_right;
                    if (cur->_right)
                        cur->_right->_parents = parents;
                }
            }
        }
        //右为空
        else if (cur->_right == nullptr)
        {
            if (parents == nullptr)
            {
                _root = _root->_left;
                if (_root)
                    _root->_parents = nullptr;
            }
            else
            {
                if (parents->_left == cur)
                {
                    parents->_left = cur->_left;
                    if (cur->_left)
                        cur->_left->_parents = parents;
                }
                else
                {
                    parents->_right = cur->_left;
                    if (cur->_left)
                        cur->_left->_parents = parents;
                }
            }
        }



        //左右均不为空，使用替代法
        else
        {
            //左子树的最右节点
            treenode<T>* subL = cur->_left;
            parents = cur;
            while (subL->_right)
            {
                parents = subL;
                subL = subL->_right;
            }
            cur->_data = subL->_data;
            if (parents->_left == subL)
            {
                parents->_left = subL->_left;
                if (subL->_left)
                    subL->_left->_parents = parents;
            }
            else
            {
                parents->_right = subL->_left;
                if (subL->_left)
                    subL->_left->_parents = parents;
            }
            cur = subL;
        }
        treenode<T>* del = cur;//cur表示删除的节点

        while (parents)
        {
            //cur就是要删除的节点
            if (cur->_col == RED)//节点为红色直接删除
            {
                break;
            }
            else//节点为黑色
            {
                if (cur->_left || cur->_right)//左不为空或右不为空，将cur左或右不为空的节点置为黑色，删除cur结束
                {
                    if (cur->_left)
                    {
                        cur->_left->_col = BLACK;
                    }
                    else
                    {
                        cur->_right->_col = BLACK;
                    }
                    break;
                }
                else//左右均为空
                {
                    //若cur不为根节点则cur一定有父节点
                    parents = cur->_parents;
                    if (flag == 1||parents->_left == cur)
                    {
                        flag = 0;
                        treenode<T>* brother = parents->_right;//肯定有兄弟节点，否则就不满足红黑树性质了
                        if (brother->_col == RED)
                        {

                            parents->_col = RED;
                            brother->_col = BLACK;
                            //brother一定有两个黑色子节点,parents一定为黑色节点
                            //旋转parents
                            rotateL(parents);
                            //继续处理新的兄弟节点
                            brother = parents->_right;
                        }
                        if(brother->_col == BLACK)//兄弟节点为黑色节点
                        {
                            //兄弟的子节点中有红色节点
                            if (brother->_left || brother->_right)//不为空则一定有红色节点
                            {
                                if (brother->_left && brother->_right == nullptr)//兄弟左子节点为红色
                                {
                                    brother->_left->_col = parents->_col;
                                    parents->_col = BLACK;
                                    brother->_col = BLACK;
                                    rotateR(brother);
                                    rotateL(parents);
                                    break;
                                }
                                else if (brother->_right && brother->_left == nullptr)//兄弟右子节点为红色
                                {
                                    brother->_right->_col = BLACK;
                                    brother->_col = parents->_col;
                                    parents->_col = BLACK;
                                    rotateL(parents);
                                    break;
                                }
                                else//兄弟左右子节点均为红色
                                {
                                    brother->_col = parents->_col;
                                    brother->_right->_col = BLACK;
                                    parents->_col = BLACK;
                                    rotateL(parents);
                                    break;
                                }
                            }
                            //兄弟的子节点中没有红色节点
                            else
                            {
                                if (parents->_col == RED)
                                {
                                    parents->_col = BLACK;
                                    brother->_col = RED;
                                    break;
                                }
                                else
                                {
                                    brother->_col = RED;
                                    cur = parents;
                                    parents = cur->_parents;
                                }
                            }
                        }
                    }
                    else if(flag == 2 || parents->_right == cur)
                    {
                        flag = 0;
                        treenode<T>* brother = parents->_left;//兄弟节点在左边
                        if (brother->_col == RED)//兄弟节点为红色节点，则其子节点一定有两个黑色节点
                        {
                            //将brother变黑，两个子节点变红
                            parents->_col = RED;
                            brother->_col = BLACK;
                            //brother一定有两个黑色子节点,parents一定为黑色节点
                            //旋转parents
                            rotateR(parents);
                            brother = parents->_left;
                        }
                        if (brother->_col == BLACK)//兄弟为黑色节点
                        {
                            if (brother->_left || brother->_right)//兄弟有红色节点
                            {
                                if (brother->_left&&brother->_right==nullptr)//兄弟的左子节点为红色节点，兄弟的右子节点为nullptr
                                {
                                    brother->_col = parents->_col;
                                    parents->_col = BLACK;
                                    brother->_left->_col = BLACK;
                                    rotateR(parents);
                                    break;
                                }
                                else if(brother->_right && brother->_left == nullptr)
                                {
                                    brother->_right->_col = parents->_col;
                                    parents->_col = BLACK;
                                    brother->_col = BLACK;
                                    rotateL(brother);
                                    rotateR(parents);
                                    break;
                                }
                                else//两个红色节点
                                {
                                    brother->_col = parents->_col;
                                    parents->_col = BLACK;
                                    brother->_left->_col = BLACK;
                                    rotateR(parents);
                                    break;
                                }
                            }
                            else//兄弟没有红色节点
                            {
                                if (parents->_col == RED)
                                {
                                    parents->_col = BLACK;
                                    brother->_col = RED;
                                    break;
                                }
                                else
                                {
                                    brother->_col = RED;
                                    cur = parents;
                                    parents = cur->_parents;
                                }
                            }
                        }
                    }
                }
            }
        }
        //不管_root根节点是什么颜色，只要该节点还存在就将其染黑
        if (_root)
            _root->_col = BLACK;
        delete del;
        return 1;
    }

    void adjustRB(treenode<T>* cur)
    {
        if (cur == _root)
            return;
        if (cur->_left || cur->_right)//左不为空或右不为空，将cur左或右不为空的节点置为黑色，删除cur结束
        {
            if (cur->_left)
            {
                cur->_left->_col = BLACK;
            }
            else
            {
                cur->_right->_col = BLACK;
            }
            break;
        }
        else//左右均为空
        {
            //若cur不为根节点则cur一定有父节点
            parents = cur->_parents;
            if (parents->_left == cur)
            {
                
                treenode<T>* brother = parents->_right;//肯定有兄弟节点，否则就不满足红黑树性质了
                if (brother->_col == RED)
                {

                    parents->_col = RED;
                    brother->_col = BLACK;
                    //brother一定有两个黑色子节点,parents一定为黑色节点
                    //旋转parents
                    rotateL(parents);
                    //继续处理新的兄弟节点
                    brother = parents->_right;
                }
                if (brother->_col == BLACK)//兄弟节点为黑色节点
                {
                    //兄弟的子节点中有红色节点
                    if (brother->_left || brother->_right)//不为空则一定有红色节点
                    {
                        if (brother->_left && brother->_right == nullptr)//兄弟左子节点为红色
                        {
                            brother->_left->_col = parents->_col;
                            parents->_col = BLACK;
                            brother->_col = BLACK;
                            rotateR(brother);
                            rotateL(parents);
                            break;
                        }
                        else if (brother->_right && brother->_left == nullptr)//兄弟右子节点为红色
                        {
                            brother->_right->_col = BLACK;
                            brother->_col = parents->_col;
                            parents->_col = BLACK;
                            rotateL(parents);
                            break;
                        }
                        else//兄弟左右子节点均为红色
                        {
                            brother->_col = parents->_col;
                            brother->_right->_col = BLACK;
                            parents->_col = BLACK;
                            rotateL(parents);
                            break;
                        }
                    }
                    //兄弟的子节点中没有红色节点
                    else
                    {
                        if (parents->_col == RED)
                        {
                            parents->_col = BLACK;
                            brother->_col = RED;
                            break;
                        }
                        else
                        {
                            brother->_col = RED;
                            cur = parents;
                            parents = cur->_parents;
                        }
                    }
                }
            }
            else if (flag == 2 || parents->_right == cur)
            {
                flag = 0;
                treenode<T>* brother = parents->_left;//兄弟节点在左边
                if (brother->_col == RED)//兄弟节点为红色节点，则其子节点一定有两个黑色节点
                {
                    //将brother变黑，两个子节点变红
                    parents->_col = RED;
                    brother->_col = BLACK;
                    //brother一定有两个黑色子节点,parents一定为黑色节点
                    //旋转parents
                    rotateR(parents);
                    brother = parents->_left;
                }
                if (brother->_col == BLACK)//兄弟为黑色节点
                {
                    if (brother->_left || brother->_right)//兄弟有红色节点
                    {
                        if (brother->_left && brother->_right == nullptr)//兄弟的左子节点为红色节点，兄弟的右子节点为nullptr
                        {
                            brother->_col = parents->_col;
                            parents->_col = BLACK;
                            brother->_left->_col = BLACK;
                            rotateR(parents);
                            break;
                        }
                        else if (brother->_right && brother->_left == nullptr)
                        {
                            brother->_right->_col = parents->_col;
                            parents->_col = BLACK;
                            brother->_col = BLACK;
                            rotateL(brother);
                            rotateR(parents);
                            break;
                        }
                        else//两个红色节点
                        {
                            brother->_col = parents->_col;
                            parents->_col = BLACK;
                            brother->_left->_col = BLACK;
                            rotateR(parents);
                            break;
                        }
                    }
                    else//兄弟没有红色节点
                    {
                        if (parents->_col == RED)
                        {
                            parents->_col = BLACK;
                            brother->_col = RED;
                            break;
                        }
                        else
                        {
                            brother->_col = RED;
                            cur = parents;
                            parents = cur->_parents;
                        }
                    }
                }
            }
        }
    }
    bool isredblacktree()
    {
        if (_root == nullptr)
            return true;
        if (_root->_col == RED)
            return false;
        int blacksize = 0;
        treenode<T>* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++blacksize;
            cur = cur->_left;
        }
        int black_path_size = 0;
        return checktree_is_red_black(_root, black_path_size, blacksize);
    }
private:
    //左旋
    void rotateL(treenode<T>* root)
    {
        treenode<T>* parents = root;
        treenode<T>* subR = parents->_right;
        parents->_right = subR->_left;
        if (subR->_left)
            subR->_left->_parents = parents;
        subR->_parents = parents->_parents;
        if (parents->_parents)
        {
            if (parents->_parents->_left == parents)
            {
                parents->_parents->_left = subR;
            }
            else
            {
                parents->_parents->_right = subR;
            }
        }
        parents->_parents = subR;
        subR->_left = parents;
        if (root == _root)
        {
            _root = subR;
        }
    }
    //右旋
    void rotateR(treenode<T>* root)
    {
        treenode<T>* parents = root;
        treenode<T>* subL = parents->_left;
        parents->_left = subL->_right;
        if (subL->_right)
            subL->_right->_parents = parents;
        subL->_parents = parents->_parents;
        if (parents->_parents)
        {
            if (parents->_parents->_left == parents)
            {
                parents->_parents->_left = subL;
            }
            else
            {
                parents->_parents->_right = subL;
            }
        }
        parents->_parents = subL;
        subL->_right = parents;
        if (root == _root)
        {
            _root = subL;
        }
    }
    treenode<T>* _root = nullptr;
};这个删除还有些问题怎么在这个基础上进行修改，变量名和总体框架不变哦