红黑树封装map和set

红黑树源代码

我们将由下列的KV模型红黑树来模拟封装STL库中的map和set

注意：为了实现封装map和set，我们需要对下列源码进行优化。

#pragma once
#include<iostream>
using namespace std;
//枚举类型的颜色分类
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)
        , _kv(kv)
        , _col(RED)
    {}
};

//红黑树类
template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    //中序遍历副函数
    void Inorder()
    {
        _Inorder(_root);
    }
    //中序遍历主函数
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << " ";
        _Inorder(root->_right);
    }


    //插入函数
    bool insert(const pair<K, V>& kv)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(kv);
            _root->_col = BLACK;//根结点一定为黑
            return true;
        }
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
        while (cur)//当不为空，说明存在值，那么继续搜索可插入的地方
        {
            if (cur->_kv.first < kv.first)//key大于结点值，往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)//key小于结点值，往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等，那么不插入，插入失败
            {
                return false;
            }
        }
        cur = new Node(kv);//新增结点
        cur->_col = RED;//默认红色
        //插入
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //开始判断颜色
        while (parent != nullptr && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            //如果父亲为红，那么违反红红规则，开始判断情况
            if (parent != nullptr && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    //变色
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //将cur和parent往上移继续判断
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//叔叔不存在或者存在且为黑色，情况二和情况三结合
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateLR(grandfather); //左右双旋
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;//根结点为黑，不需要往上了
                }
            }
            else//parent在grandfather的右边
            {
                Node* uncle = grandfather->_left;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //向上调整
                    cur = grandfather;
                    parent = grandfather->_parent;
                }
                else//叔叔不存在或者存在且为黑色，情况二和情况三结合
                {
                    if (cur == parent->_left)//如果插入在parent的左边
                    {
                        RotateRL(grandfather);//右左双旋
                        cur->_col = BLACK;
                        grandfather->_col = RED;

                    }
                    else//如果插入在parent的右边
                    {
                        RotateL(grandfather);//左旋
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    break;//根结点为黑，不需要往上了
                }
            }
        }
        _root->_col = BLACK;//往上移动后无论cur是否为根结点，统一为改黑

        return true;//插入成功

    }

    //左单旋
    void RotateL(Node* parent)
    {
        //定义新指针，方便操作
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* pp = parent->_parent;//方便更改_root的操作

        parent->_right = subRL;//让parent结点链接subRL
        subR->_left = parent;//让subR的左子树链接parent
        parent->_parent = subR;//由于parent的_parent由nullptr变成了subR，所以也需要重新链接
        if (subRL)
            //判断subRL是否为空，如果为空的话就不需要对subRL进行操作了，不然会出现对空指针进行解引用的问题
        {
            subRL->_parent = parent;//不为空，那么让subRL链接parent
        }
        if (pp == nullptr)//如果parent是整棵树的根结点
        {
            _root = subR;//subR变为根结点
            subR->_parent = nullptr;//subR的_parent为空
        }
        else//如果parent不是整棵树的根结点，那么将新的parent重新链接上一个结点
        {
            if (pp->_left = parent)//如果parent是上一个结点的左子树，那么新的parent也是
            {
                pp->_left = subR;
            }
            else//如果parent是上一个结点的右子树，那么新的parent也是
            {
                pp->_right = subR;
            }
            subR->_parent = pp;//更新subR的父结点
        }
        //parent->_bf = subR->_bf = 0;//由于旋转后，整棵树的高度变回插入前的，那么此时parent和subR(cur)的因子都变回0
    }

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;
        Node* pp = parent->_parent;

        //建立subL和parent之间的关系
        parent->_left = subRR;
        subL->_right = parent;

        //建立parent和subRR之间的关系
        parent->_parent = subL;
        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }

        //建立PP和subL之间的关系
        if (pp == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        //更新平衡因子
        //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 == 0)
        //{
        //    //subLR自己就是新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subLR的左子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subLR的右子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = -1;
        //    parent->_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 == 0)
        //{
        //    //subRL自己就是新增
        //    parent->_bf = subR->_bf = subRL->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subRL的左子树新增
        //    parent->_bf = 0;
        //    subRL->_bf = 0;
        //    subR->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subRL的右子树新增
        //    parent->_bf = -1;
        //    subRL->_bf = 0;
        //    subR->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    // blacknum是根结点到当前结点的黑色结点数量
    bool check(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)
        {
            ++blacknum;
        }

        return check(root->_left,blacknum,count) && check(root->_right,blacknum,count);
    }

    bool isbalance()
    {
        if (_root == nullptr)
        {
            return true;
        }
        if (_root->_col == RED)
        {
            return false;
        }
        //找最左路径作为黑色结点数目的参考值
        Node* cur = _root;
        int count = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++count;
            cur = cur->_left;
        }

        int blacknum = 0;
        return check(_root,blacknum,count); 
    }
private:
    Node* _root = nullptr;
};

红黑树的模板

首先，我们要知道，set是K模型，map是KV模型，那么如何用一颗红黑树同时封装出两种模型呢？这时候就应该想到模板了。

我们需要对红黑树类模板进行修改：

这是原始代码：

template<class K, class V>
class RBTree

 这是修改后的代码：

template<class K, class T, class KeyofT>
class RBTree

可以看到，这将V变为T，然后多出了KeyofT，这是什么意思呢？

class V    --->    class T

set是K模型，map是KV模型

在set容器中,T是对应着key：

    template<class K>
    class set
    {
    public:
    //...
    private:
        RBTree<K, K, SetKeyofT> _t;
    };

在map容器中,T是对应着key和value组成的键值对：

    template<class K,class V>
    class map
    {
    public:
    //...
    private:
        RBTree<K, pair<K, V>, MapKeyofT> _t;
    };

 

这时候会有一个疑问，能不能把第一个参数：class K 给去掉，因为在set中，K已经重复了；在map中，貌似键值对里也已经包含着key和value了？

可以肯定地说：不能去掉！在set中，确实可以省略不要；但是在map中，有些容器接口需要给出key的类型，那么在键值对中，我们只能取到key的值。所以在map中不能删去。

所以，我们更改了红黑树源码中的结点类实现

结点类实现

//定义一个结构体结点
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)
        , _data(data)
        , _col(RED)
    {}
};

可以看到，这里的 T _data就是新增的，T对应set中的key，map中的键值对。

  map、set中的仿函数

class KeyofT

 在上述set和map容器的私有成员中，分别有着：

 在map和set分别传入底层红黑树时，T传入的可能是key，也可能是key和value的键值对，如果是键值对，那么就需要将键值对的key提取出来再进行比较，那么此时就需要用到仿函数。

map容器：

    template<class K,class V>
    class map
    {
    public:
        struct MapKeyofT
        {
            const K& operator()(const pair<K,V>& kv)
            {
                return kv.first;
            }
        };
    private:
        RBTree<K, pair<K, V>, MapKeyofT> _t;
    };

set容器：

    template<class K>
    class set
    {
    public:
        struct SetKeyofT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    private:
        RBTree<K, K, SetKeyofT> _t;
    };

可以看到，我们在这个仿函数中重载了operator()， 这个operator()在map中用来提取kv.first，也就是key值，为了能统一map和set，我们在set也重载了operator()。

所以set传入底层红黑树就是set的仿函数，map传入底层红黑树就是map的仿函数。

那么应该怎么用呢？

例如在insert插入函数中，我们需要获取结点内的key值进行比较大小

新定义了一个kot：

KeyofT kot;

这是其中一小段代码：

if (kot(cur->_data) < kot(data))//key大于结点值，往右走

这里可以调用仿函数，如果_data/data类型是key，那么在仿函数中直接就返回key；如果类型是键值对，那么就返回kv.first

迭代器类实现

在迭代器中,解引用操作就是获取结点的数据的引用，->操作就是获取结点数据的地址即可。

真正有难度的是++和--：

在树中的++和--是按照中序遍历的方式进行的，也就是让指针按照 左子树-根-右子树 的顺序移动。

在++操作中：

如果右子树不为空，那么进入右子树然后寻找最左结点。

如果右子树为空，那么往上返回父亲节点，然后找到当前结点不是父亲结点的右子树的父亲节点。

在--操作中：

如果左子树不为空，那么进入右子树然后寻找最右结点。

如果左子树为空，那么往上返回父亲节点，然后找到当前结点不是父亲结点的左子树的父亲节点。

//迭代器类
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;//返回结点数据的引用
    }

    Ptr operator->()
    {
        return &_node->_data;//返回结点数据的地址
    }

    Self operator++()
    {
        if (_node->_right)//如果右子树存在
        {
            Node* cur = _node->_right;//则进入右子树
            while (cur->_left)//找到右子树的最左结点
            {
                cur = cur->_left;
            }
            _node = cur;//更新当前结点
        }
        else//如果右子树不存在
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)//父亲结点存在且当前结点为父亲结点的右子树
            {
                //不断往上循环
                cur = parent;
                parent = parent->_parent;
            }
            //当前结点不是父亲的右子树时，更新指针指向当前结点的父亲结点
            _node = parent;
        }
        return *this;
    }


    Self operator--()
    {
        if (_node->_left) //结点的左子树不为空
        {
            //寻找该结点左子树当中的最右结点
            Node* right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }
            _node = right; //--后变为该结点
        }
        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; //判断两个正向迭代器所封装的结点是否是同一个
	}
};

迭代器函数实现 

在树中的begin()和end()也有着不同的规则：

begin()获取的是树的最左结点。

end()获取的是树的最右结点的后一个结点，也就是空结点。

    //迭代器函数
    typedef _TreeIterator<T,T&,T*> iterator;
    typedef _TreeIterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
        Node* cur = _root;
        while (cur && cur->_left)//寻找最左结点
        {
            cur = cur->_left;
        }

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

    const_iterator begin() const
    {
        Node* cur = _root;
        while (cur && cur->_left)//寻找最左结点
        {
            cur = cur->_left;
        }

        return iterator(cur);
    }
    const_iterator end() const
    {
        return iterator(nullptr);
    }

优化后的红黑树源码

#pragma once
#include<iostream>
using namespace std;
//枚举类型的颜色分类
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)
        , _data(data)
        , _col(RED)
    {}
};

//迭代器类
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;
    }

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

    Self operator++()
    {
        if (_node->_right)
        {
            Node* cur = _node->_right;
            while (cur->_left)
            {
                cur = cur->_left;
            }
            _node = cur;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self operator--()
    {
        if (_node->_left) //结点的左子树不为空
        {
            //寻找该结点左子树当中的最右结点
            Node* right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }
            _node = right; //--后变为该结点
        }
        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; //判断两个正向迭代器所封装的结点是否是同一个
    }
};


//红黑树类
template<class K, class T, class KeyofT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    //中序遍历副函数
    void Inorder()
    {
        _Inorder(_root);
    }
    //中序遍历主函数
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << " ";
        _Inorder(root->_right);
    }

    //迭代器函数
    typedef _TreeIterator<T,T&,T*> iterator;
    typedef _TreeIterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
        Node* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }

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

    const_iterator begin() const
    {
        Node* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }

        return iterator(cur);
    }
    const_iterator end() const
    {
        return iterator(nullptr);
    }


    //插入函数
    pair<iterator,bool> insert(const T& data)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(data);
            _root->_col = BLACK;//根结点一定为黑
            return make_pair(iterator(_root),true);
        }
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
        KeyofT kot;

        while (cur)//当不为空，说明存在值，那么继续搜索可插入的地方
        {
            if (kot(cur->_data) < kot(data))//key大于结点值，往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kot(cur->_data) > kot(data))//key小于结点值，往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等，那么不插入，插入失败
            {
                return make_pair(iterator(cur), false);
            }
         }
        cur = new Node(data);//新增结点
        Node* newnode = cur;
        cur->_col = RED;//默认红色
        //插入
        if (kot(parent->_data) > kot(data))
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //开始判断颜色
        while (parent != nullptr && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            //如果父亲为红，那么违反红红规则，开始判断情况
            if (parent != nullptr && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    //变色
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //将cur和parent往上移继续判断
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//叔叔不存在或者存在且为黑色，情况二和情况三结合
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateLR(grandfather); //左右双旋
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;//根结点为黑，不需要往上了
                }
            }
            else//parent在grandfather的右边
            {
                Node* uncle = grandfather->_left;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //向上调整
                    cur = grandfather;
                    parent = grandfather->_parent;
                }
                else//叔叔不存在或者存在且为黑色，情况二和情况三结合
                {
                    if (cur == parent->_left)//如果插入在parent的左边
                    {
                        RotateRL(grandfather);//右左双旋
                        cur->_col = BLACK;
                        grandfather->_col = RED;

                    }
                    else//如果插入在parent的右边
                    {
                        RotateL(grandfather);//左旋
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    break;//根结点为黑，不需要往上了
                }
            }
        }
        _root->_col = BLACK;//往上移动后无论cur是否为根结点，统一为改黑

        return make_pair(iterator(newnode), true);//插入成功

    }

    //左单旋
    void RotateL(Node* parent)
    {
        //定义新指针，方便操作
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* pp = parent->_parent;//方便更改_root的操作

        parent->_right = subRL;//让parent结点链接subRL
        subR->_left = parent;//让subR的左子树链接parent
        parent->_parent = subR;//由于parent的_parent由nullptr变成了subR，所以也需要重新链接
        if (subRL)
            //判断subRL是否为空，如果为空的话就不需要对subRL进行操作了，不然会出现对空指针进行解引用的问题
        {
            subRL->_parent = parent;//不为空，那么让subRL链接parent
        }
        if (pp == nullptr)//如果parent是整棵树的根结点
        {
            _root = subR;//subR变为根结点
            subR->_parent = nullptr;//subR的_parent为空
        }
        else//如果parent不是整棵树的根结点，那么将新的parent重新链接上一个结点
        {
            if (pp->_left = parent)//如果parent是上一个结点的左子树，那么新的parent也是
            {
                pp->_left = subR;
            }
            else//如果parent是上一个结点的右子树，那么新的parent也是
            {
                pp->_right = subR;
            }
            subR->_parent = pp;//更新subR的父结点
        }
        //parent->_bf = subR->_bf = 0;//由于旋转后，整棵树的高度变回插入前的，那么此时parent和subR(cur)的因子都变回0
    }




    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;
        Node* pp = parent->_parent;

        //建立subL和parent之间的关系
        parent->_left = subRR;
        subL->_right = parent;

        //建立parent和subRR之间的关系
        parent->_parent = subL;
        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }

        //建立PP和subL之间的关系
        if (pp == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        //更新平衡因子
        //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 == 0)
        //{
        //    //subLR自己就是新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subLR的左子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subLR的右子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = -1;
        //    parent->_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 == 0)
        //{
        //    //subRL自己就是新增
        //    parent->_bf = subR->_bf = subRL->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subRL的左子树新增
        //    parent->_bf = 0;
        //    subRL->_bf = 0;
        //    subR->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subRL的右子树新增
        //    parent->_bf = -1;
        //    subRL->_bf = 0;
        //    subR->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    // blacknum是根结点到当前结点的黑色结点数量
    bool check(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)
        {
            ++blacknum;
        }

        return check(root->_left, blacknum, count) && check(root->_right, blacknum, count);
    }

    bool isbalance()
    {
        if (_root == nullptr)
        {
            return true;
        }
        if (_root->_col == RED)
        {
            return false;
        }
        //找最左路径作为黑色结点数目的参考值
        Node* cur = _root;
        int count = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++count;
            cur = cur->_left;
        }

        int blacknum = 0;
        return check(_root, blacknum, count);
    }
private:
    Node* _root = nullptr;
};

用红黑树封装set的容器

#pragma once
#include"RBTree.h"

namespace bear
{
    template<class K>
    class set
    {
    public:
        //仿函数
        struct SetKeyofT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
        //红黑树最好不要修改，将普通迭代器和const迭代器都用const迭代器重命名
        typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;
        typedef typename RBTree<K, K, SetKeyofT>::const_iterator const_iterator;

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

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

    private:
        RBTree<K, K, SetKeyofT> _t;
    };
}

 用红黑树封装map的容器

在map中，还需要对[]运算符进行重载。

#pragma once
#include"RBTree.h"

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

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/645595.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Collection

Collection

Collection是单列集合的祖宗接口&#xff0c;它的功能是全部单列集合都可以继承使用。 1.添加元素 public class test {public static void main(String [] args) {Collection<String> colnew ArrayList<>();col.add("aaa");col.add("bbb");…
阅读更多...
多签名钱包

多签名钱包

相交于硬件钱包的物理上丢失和密钥遗忘&#xff0c;多签名钱包在保证安全不易被破解的基础上&#xff0c;解决了部分密钥丢失的问题。 相比于BTC之前讲到的脚本钱包&#xff08;BTC—脚本&#xff09;&#xff0c;ETH的多签钱包设计可以通过智能合约来实现 设计思路 工作原理…
阅读更多...
辐射度技术在AI去衣中的魅力与科学

辐射度技术在AI去衣中的魅力与科学

引言&#xff1a; 在当今的数字化时代&#xff0c;人工智能正逐渐渗透到我们生活的方方面面。其中&#xff0c;AI去衣技术作为一项颇具争议但又不失其科技创新的应用&#xff0c;正引起越来越多的关注和讨论。而在实现高质量图像渲染的过程中&#xff0c;辐射度技术凭借其卓越的…
阅读更多...
移动端开发 笔记01

移动端开发 笔记01

目录 01 移动端的概述 02 移动端的视口标签 03 开发中的二倍图 04 流式布局 05 弹性盒子布局 01 移动端的概述 移动端包括:手机 平板 便携式设备 目前主流的移动端开发: 安卓设备 IOS设备 只要移动端支持浏览器 那么就可以使用浏览器开发移动端项目 开发移动端 使用…
阅读更多...
GNSS中的多路径效应原理及计算方法

GNSS中的多路径效应原理及计算方法

1 多路径效应原理 图1 多路径效应原理图 2 计算方法 如需原文&#xff0c;可加多源融合定位与智能控制讨论群获取,QQ群号&#xff1a;51885949
阅读更多...
6、phpjm混淆解密和php反序列化

6、phpjm混淆解密和php反序列化

题目&#xff1a;青少年雏形系统 1、打开链接也是一个登入面板 2、尝试了sqlmap没头绪 3、尝试御剑&#xff0c;发现一个www.zip 4、下载打开&#xff0c;有一个php文件打开有一段phpjm混淆加密 5、使用手工解混淆 具体解法链接&#xff1a;奇安信攻防社区-phpjm混淆解密浅谈…
阅读更多...
页面＜html＞上多了一个滚动条，定位发现是＜body＞里面多了一个id为trans-tooltip的div

页面＜html＞上多了一个滚动条，定位发现是＜body＞里面多了一个id为trans-tooltip的div

现象分析&#xff1a; 页面根标签html多了一个滚动条&#xff0c;发现body里面多了一个id为trans-tooltip的div&#xff0c;虽然width为0&#xff0c;height为0&#xff0c;但是其子元素还是有高度&#xff0c;占据了空间&#xff0c;最终导致了滚动条&#xff1b; 根本原因&…
阅读更多...
SpringBoot注解--09--idea创建spring boot项目，java版本只能选择17和21

SpringBoot注解--09--idea创建spring boot项目，java版本只能选择17和21

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 idea创建spring boot项目1.问题描述2.原因3.解决方法方案一&#xff1a;升级JDK版本至17或更高方案二&#xff1a;替换Spring初始化的源https://start.aliyun.com i…
阅读更多...
可以在搜索结果中屏蔽指定网站的插件

可以在搜索结果中屏蔽指定网站的插件

可以在搜索结果中屏蔽指定网站的插件 | LogDict背景 在搜索引擎中搜索问题, 往往充斥各种无效内容 比如搜个技术类的问题, 前几页CSDN, 百度百家号, 百度经验, 百度知道, 腾讯云各类云爬的水文 CSDN基本都是复制粘贴的, 甚至格式都乱码了, 虽然我以前也干过 要复制粘贴无所谓, …
阅读更多...
语文学习笔记6——陶侃之母

语文学习笔记6——陶侃之母

阅读更多...
最小二乘法-超详细推导（转换为矩阵乘法推导，矩阵求导推导）

最小二乘法-超详细推导（转换为矩阵乘法推导，矩阵求导推导）

最小二乘法就是让均方误差最小。 下面是损失函数转换为矩阵方式的详解 如何让其最小&#xff0c;在导数为0的地方取极小值。 问&#xff1a;导数为0的地方可能去极大值&#xff0c;也可能是极小值&#xff0c;凭什么说导数为0就是极小值&#xff1f; 答&#xff1a;因为使用…
阅读更多...
Linux 生产跑批脚本解读

Linux 生产跑批脚本解读

1.查看定时任务 2.脚本-目录结构 1&#xff09;config.ini 2&#xff09;run.sh 3.命令解读 1&#xff09;ls -1 路径文件夹 含义&#xff1a;ls -1 /home/oracle/shell/config/ 将文件夹config内的文件全部列出 [oracleneptune config]$ ls -1 /home/oracle/shel…
阅读更多...
【ROS机器人学习】--------1ROS工作空间和功能包创建

【ROS机器人学习】--------1ROS工作空间和功能包创建

虚拟机工具和镜像链接: https://pan.baidu.com/s/1HDmpbMESiUA2nj3qFVyFcw?pwd8686 提取码: 8686 ROS工作空间是一个用于组织和管理ROS&#xff08;机器人操作系统&#xff09;包的目录结构&#xff0c;它通常包含多个子目录&#xff0c;用于存放源码、构建文件和安装文件。工…
阅读更多...
Elastic Cloud 将 Elasticsearch 向量数据库优化配置文件添加到 Microsoft Azure

Elastic Cloud 将 Elasticsearch 向量数据库优化配置文件添加到 Microsoft Azure

作者&#xff1a;来自 Elastic Serena Chou, Jeff Vestal, Yuvraj Gupta 今天&#xff0c;我们很高兴地宣布&#xff0c;我们的 Elastic Cloud Vector Search 优化硬件配置文件现已可供 Elastic Cloud on Microsoft Azure 用户使用。 此硬件配置文件针对使用 Elasticsearch 作…
阅读更多...
CSS单位px、rem、em、vw、vh的区别

CSS单位px、rem、em、vw、vh的区别

目录 前言 零.视口介绍 一.px 二.em 三.rem【重要】 3.1rem介绍 3.2rem与em的区别 四.vw、vh、vmax、vmin 五.注意问题 5.1如何使1rem 10px&#xff1f; 5.2如果父元素没有指定高度&#xff0c;那么子元素的百分比高度是多少&#xff1f; 5.3更多问题 前言 这几…
阅读更多...
实现多级树形结构查询 比如分类（父分类、子分类）

实现多级树形结构查询 比如分类（父分类、子分类）

实现多级树形结构查询 比如分类&#xff08;父分类、子分类&#xff09; 数据库表结构 CREATE TABLE course_category (id varchar(20) NOT NULL COMMENT 主键,name varchar(32) NOT NULL COMMENT 分类名称,label varchar(32) DEFAULT NULL COMMENT 分类标签默认和名称一样,p…
阅读更多...
CLIP 论文的关键内容

CLIP 论文的关键内容

CLIP 论文整体架构 该论文总共有 48 页&#xff0c;除去最后的补充材料十页去掉&#xff0c;正文也还有三十多页&#xff0c;其中大部分篇幅都留给了实验和响应的一些分析。 从头开始的话&#xff0c;第一页就是摘要&#xff0c;接下来一页多是引言&#xff0c;接下来的两页就…
阅读更多...
qt-C++笔记之QThread使用

qt-C++笔记之QThread使用

qt-C笔记之QThread使用 ——2024-05-26 下午 code review! 参考博文&#xff1a; qt-C笔记之使用QtConcurrent异步地执行槽函数中的内容&#xff0c;使其不阻塞主界面 qt-C笔记之QThread使用 文章目录 qt-C笔记之QThread使用一:Qt中几种多线程方法1.1. 使用 QThread 和 Lambda…
阅读更多...
gnocchi学习小结

gnocchi学习小结

背景 总结gnocchi 4.4版本gnocchi-metricd工作流程 入口 gnocchi.cli.metricd metricd stop after processing metric默认为0&#xff0c;调servicemanager run MetricdServiceManager __init__ 服务逻辑封装到MetricdServiceManager初始化中 主要由MetricProcessor, Met…
阅读更多...
火山引擎“奇袭”阿里云

火山引擎“奇袭”阿里云

图片&#xff5c;电影《美国队长3》剧照 ©自象限原创 作者丨程心 编辑丨罗辑 大模型价格战&#xff0c;已经不是什么新闻。 从OpenAI发布GPT-4o&#xff0c;将API价格下调50%&#xff0c;并宣布面向普通用户免费开始&#xff0c;就标志着大模型的竞争从性能进入到了成本…
阅读更多...
最新文章

Copyright @ 2022~2023