当前位置： 首页 > article >正文

封装红黑树-＞mapset

article 2025/3/17 5:10:33

目录

目录

1.KeyofT

2.iterator

3.key不支持修改问题

4.map的operator[ ]

5.map实现

6.set实现

7.封装后的红黑树

小知识

由于set为单模版参数，map为双模版参数，所以为了只实现一棵红黑树，对红黑树进行了一些处理

1.KeyofT

获取key值，用来实现比较逻辑，在set和map中要分别实现一个。

set中：

struct KeyofT
{
    const T& operator()(const T& key)
    {
        return key;
    }
};

map中：

    struct KeyofV
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };

2.iterator

这里使用带头结点的红黑树。

++：右子树不为空时，下一个访问右子树的最左结点；为空，下一个访问孩子是父亲的左结点的父亲结点。

--：左子树不为空时，下一个访问左子树的最右结点；为空，下一个访问孩子节点时父亲的右结点的父亲结点

和list中的封装类似，++和--的逻辑不同。

template<class T,class ref,class ptr>
struct RBTree_Iterator
{
    typedef RBTree_node<T> Node;
    Node* _node;
    Node* _root;
    typedef RBTree_Iterator<T, ref, ptr> self;

    RBTree_Iterator(Node* node, Node* root)
        :_node(node)
        ,_root(root)
    {}

    self& operator++()
    {
        if (_node->_right)
        {
            _node = _node->_right;
            while (_node->_left)
            {
                _node = _node->_left;
            }
        }
        else
        {
            if (_node != _root)
            {
                Node* parent = _node->_parent;
                while (parent->_left != _node)
                {
                    if (parent == _root)
                    {
                        _node = nullptr;
                        return *this;
                    }
                    _node = parent;
                    parent = _node->_parent;
                }
                _node = parent;
            }
            else
            {
                _node = nullptr;
            }
        }
        return *this;
    }

    self& operator--()
    {
        if (!_node)
        {
            _node = _root->_parent->_right;
        }
        else if (_node->_left)
        {
            _node = _node->_left;
            while (_node->_right)
            {
                _node = _node->_right;
            }
        }
        else
        {
            if (_node != _root)
            {
                Node* parent = _node->_parent;
                while (parent->_right != _node)
                {
                    if (parent == _root)
                    {
                        _node = nullptr;
                        break;
                    }
                    _node = parent;
                    parent = _node->_parent;
                }
                _node = parent;
            }
            else
            {
                _node = nullptr;
            }
        }
        return *this;
    }

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

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

    bool operator==(const self& Iterator)
    {
        return _node == Iterator._node;
    }

    bool operator!=(const self& Iterator)
    {
        return _node != Iterator._node;
    }

};

3.key不支持修改问题

由于我们在使用树时，key值是不允许修改的，所以要在构造红黑树对象时，传入constkey

map中： RBTree<K, pair<const K, V>, KeyofV> _root;

typedef typename RBTree<K, pair<const K,V>, KeyofV>::Iterator iterator;
typedef typename RBTree<K, pair<const K,V>, KeyofV>::const_Iterator const_iterator;

set中：  RBTree<T,const T, KeyofT> _root;
typedef typename RBTree<T, const T, KeyofT>::Iterator iterator;
typedef typename RBTree<T, const T, KeyofT>::const_Iterator const_iterator;

4.map的operator[ ]

迭代器实现后这个重载很简单

V& operator[](const K& key)
{
    return insert(make_pair(key, V())).first->second;
}

5.map实现

include了红黑树的头文件

template<class K,class V>
class mymap
{
    struct KeyofV
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };

    RBTree<K, pair<const K, V>, KeyofV> _root;

public:
    typedef typename RBTree<K, pair<const K,V>, KeyofV>::Iterator iterator;
    typedef typename RBTree<K, pair<const K,V>, KeyofV>::const_Iterator const_iterator;

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

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

    const_iterator begin() const
    {
        return _root.cbegin();
    }

    const_iterator end() const
    {
        return _root.cend();
    }

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

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

    V& operator[](const K& key)
    {
        return insert(make_pair(key, V())).first->second;
    }

};

6.set实现

include了红黑树的头文件

template<class T>
class myset
{
    struct KeyofT
    {
        const T& operator()(const T& key)
        {
            return key;
        }
    };
    
    RBTree<T,const T, KeyofT> _root;
public:
    typedef typename RBTree<T, const T, KeyofT>::Iterator iterator;
    typedef typename RBTree<T, const T, KeyofT>::const_Iterator const_iterator;


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

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

    const_iterator begin() const
    {
        return _root.cbegin();
    }

    const_iterator end() const
    {
        return _root.cend();
    }

    pair<iterator,bool> insert(const T& key)
    {
        return _root.insert(key);
    }

    iterator find(const T& key)
    {
        return _root.find(key);
    }
};

7.封装后的红黑树

enum color
{
    red,
    black
};

template<class T>
struct RBTree_node
{
    T _data;
    RBTree_node<T>* _left = nullptr;
    RBTree_node<T>* _right = nullptr;
    RBTree_node<T>* _parent = nullptr;
    color _color = black;

    RBTree_node(const T& data = T())
        :_data(data)
    {}
};

template<class T,class ref,class ptr>
struct RBTree_Iterator
{
    typedef RBTree_node<T> Node;
    Node* _node;
    Node* _root;
    typedef RBTree_Iterator<T, ref, ptr> self;

    RBTree_Iterator(Node* node, Node* root)
        :_node(node)
        ,_root(root)
    {}

    self& operator++()
    {
        if (_node->_right)
        {
            _node = _node->_right;
            while (_node->_left)
            {
                _node = _node->_left;
            }
        }
        else
        {
            if (_node != _root)
            {
                Node* parent = _node->_parent;
                while (parent->_left != _node)
                {
                    if (parent == _root)
                    {
                        _node = nullptr;
                        return *this;
                    }
                    _node = parent;
                    parent = _node->_parent;
                }
                _node = parent;
            }
            else
            {
                _node = nullptr;
            }
        }
        return *this;
    }

    self& operator--()
    {
        if (!_node)
        {
            _node = _root->_parent->_right;
        }
        else if (_node->_left)
        {
            _node = _node->_left;
            while (_node->_right)
            {
                _node = _node->_right;
            }
        }
        else
        {
            if (_node != _root)
            {
                Node* parent = _node->_parent;
                while (parent->_right != _node)
                {
                    if (parent == _root)
                    {
                        _node = nullptr;
                        break;
                    }
                    _node = parent;
                    parent = _node->_parent;
                }
                _node = parent;
            }
            else
            {
                _node = nullptr;
            }
        }
        return *this;
    }

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

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

    bool operator==(const self& Iterator)
    {
        return _node == Iterator._node;
    }

    bool operator!=(const self& Iterator)
    {
        return _node != Iterator._node;
    }

};

template<class K,class T,class KeyofT>
class RBTree
{
    typedef RBTree_node<T> node;
    node* _phead;

    node* Copy(node* root)
    {
        if (!root)
            return nullptr;

        node* newroot = new node(root->_data);
        newroot->_color = root->_color;
        newroot->_left = Copy(root->_left);
        newroot->_right = Copy(root->_right);

        return newroot;
    }

    void Destory(node* root)
    {
        if (!root)
            return;

        Destory(root->_left);
        Destory(root->_right);
        delete root;
    }

    void rotateL(node* root)
    {
        node* child = root->_right;
        node* childchild = child->_left;
        node* rootparent = root->_parent;
        node* _root = getroot();

        root->_right = childchild;
        if (childchild) childchild->_parent = root;

        child->_parent = rootparent;
        if (root == _root) rootparent->_parent = child;
        else
        {
            if (rootparent->_left == root) rootparent->_left = child;
            else if (rootparent->_right == root) rootparent->_right = child;
            else assert(false);
        }
        root->_parent = child;
        child->_left = root;
    }

    void rotateR(node* root)
    {
        node* child = root->_left;
        node* childchild = child->_right;
        node* rootparent = root->_parent;
        node* _root = getroot();

        root->_left = childchild;
        if (childchild) childchild->_parent = root;

        child->_parent = rootparent;
        if (root == _root) rootparent->_parent = child;
        else
        {
            if (rootparent->_left == root) rootparent->_left = child;
            else if (rootparent->_right == root) rootparent->_right = child;
            else assert(false);
        }
        root->_parent = child;
        child->_right = root;
    }

    void rotateLR(node* root)
    {
        node* orootp = root->_parent;
        rotateL(root);
        rotateR(orootp);
    }

    void rotateRL(node* root)
    {
        node* orootp = root->_parent;
        rotateR(root);
        rotateL(orootp);
    }

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

    size_t _size(node* root)
    {
        if (!root) return 0;
        return _size(root->_left) + _size(root->_right) + 1;
    }

    node* getroot()
    {
        if (_phead->_parent)
            return _phead->_parent;
        return nullptr;
    }

    const node* getroot()const //记得重载const版本，不然会出错
    {
        return _phead->_parent ? _phead->_parent : nullptr;
    }

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

    RBTree()
    {
        _phead = new node;
        _phead->_left = _phead->_right = _phead;
    };

    /*RBTree(const RBTree<K,T,KeyofT>& tmp)
    {
        _phead->_parent = Copy(tmp._phead->_parent);
        if (_phead->_parent) _phead->_parent->_parent = _phead;
    }

    RBTree<K, T, KeyofT>& operator=(RBTree<K,T,KeyofT> tmp)
    {
        swap(_phead, tmp._phead);
        return *this;
    }*/

    ~RBTree()
    {
        Destory(getroot());
        delete _phead;
        _phead = nullptr;
    }

//iterator
    Iterator begin()
    {
        node* _root = getroot();
        if(_root)
        return Iterator(_phead->_left, _root);
        return Iterator(_root, _root);
    }

    Iterator end()
    {
        return Iterator(nullptr, getroot());
    }

    const_Iterator cbegin() const
    {
        const node* _root = getroot();
        if (_root)
            return const_Iterator(_phead->_left, const_cast<node*>(_root));
        return const_Iterator(const_cast<node*>(_root), const_cast<node*>(_root));
    }

    const_Iterator cend() const
    {
        return const_Iterator(nullptr, const_cast<node*>(getroot()));
    }

    pair<Iterator,bool> insert(const T& data)
    {
        node* _root = getroot();
        KeyofT kot;//获取key值用来比较

        if (!_root) {
            _root = new node(data);
            _phead->_parent = _phead->_left = _phead->_right = _root;
            _root->_parent = _phead;
            return make_pair(Iterator(_root, _root), true);
        }
        else
        {
            node* cur = _root;
            node* newnode = new node(data);
            node* parent = _root;
            newnode->_color = red;

            while (cur)
            {
                if (kot(data) > kot(cur->_data))
                {
                    cur = cur->_right;
                    if (cur)
                        parent = parent->_right;
                }
                else if (kot(data) < kot(cur->_data))
                {
                    cur = cur->_left;
                    if (cur)
                        parent = parent->_left;
                }
                else
                    return make_pair(Iterator(cur,_root), false);
            }

            node* u = nullptr;
            newnode->_parent = parent;


            if (kot(parent->_data) < kot(data))
            {
                parent->_right = newnode;
            }
            else if (kot(parent->_data) > kot(data))
            {
                parent->_left = newnode;
            }

            if (newnode == _phead->_left->_left) _phead->_left = newnode;
            if (newnode == _phead->_right->_right) _phead->_right = newnode;//维护头结点的左右指针

            node* g = parent->_parent;
            cur = newnode;
            while (g)
            {
                if (parent->_color == black)
                    break;
                else
                {
                    if (g->_left == parent) u = g->_right;
                    else u = g->_left;
                    if (u && u->_color == red)
                    {
                        g->_color = red;
                        parent->_color = u->_color = black;
                        //更新cur g parent u
                        cur = g; parent = cur->_parent;
                        if (!parent) break;
                        g = parent->_parent;
                    }
                    else
                    {
                        if (parent->_left == cur && g->_left == parent)
                        {
                            rotateR(g); parent->_color = black; g->_color = red;
                        }
                        else if (parent->_right == cur && g->_right == parent)
                        {
                            rotateL(g); parent->_color = black; g->_color = red;
                        }
                        else if (parent->_right == cur && g->_left == parent)
                        {
                            rotateLR(parent); g->_color = red; cur->_color = black;
                        }
                        else if (parent->_left == cur && g->_right == parent)
                        {
                            rotateRL(parent); g->_color = red; cur->_color = black;
                        }
                        break;
                    }
                }
            }
            getroot()->_color = black;
            return make_pair(Iterator(newnode, _root), true);
        }
    }

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

    int Size()
    {
        return _size(getroot());
    }

    node* leftmin()
    {
        return _phead->_left;
    }

    node* rightmax()
    {
        return _phead->_right;
    }

    Iterator find(const T& data)
    {
        KeyofT kot;
        node* cur = getroot();
        while (cur)
        {
            if (kot(cur->_data) < kot(data))
                cur = cur->_right;
            else if (kot(cur->_data) > kot(data))
                cur = cur->_left;
            else
                return Iterator(cur, getroot());
        }
        return Iterator(nullptr, getroot());
    }

    bool blacknum(node* root, int sum, int num)
    {
        if (!root)
        {
            if (num == 0) num = sum;
            return num == sum;
        }

        if (root->_color == black) sum += 1;
        return blacknum(root->_left, sum, num) && blacknum(root->_right, sum, num);

    }

    bool singlered(node* root)
    {
        if (!root) return true;

        if (root->_color == red && root->_parent->_color == red) return false;
        return singlered(root->_left) && singlered(root->_right);
    }

    bool IsBalanceTree()
    {
        node* _root = getroot();
        if (!_root) return true;
        if (_root->_color != black) return false;

        if (!blacknum(_root, 0, 0)) return false;
        if (!singlered(_root)) return false;
        return true;
    }


};

小知识

1.C++可以使用范围for来遍历数组，相当于使用指针（特殊的迭代器）来遍历

2.java/c++中   负数 % 整数  =  负数      a%p = n  ----》修正 = （a%p+p）%p 使结果为正


http://www.kler.cn/a/587915.html

相关文章：

  • 个人学习编程(3-16) leetcode刷题
  • generallseteter插件生成内容和数据库不一致
  • GPT 1-3（速通版）
  • 第36周：文献阅读
  • [oeasy]python074_ai辅助编程_水果程序_fruits_apple_banana_加法_python之禅
  • ssrf总结
  • Windows 上安装配置 Apache Tomcat 及Tomcat 与 JDK 版本对应
  • OpenAI定义的Agent新范式如何构建自动化系统
  • jsonl与json区别
  • 卷积神经网络（CNN）的主要架构
  • leetcode 75.颜色分类（荷兰国旗问题）
  • 【胶囊网络】完美复现Hinton论文99.23%
  • 社区版Uos20.9从源码编译QT5.15.2
  • 【商城实战(33)】解锁版本迭代与更新策略
  • 网络华为HCIA+HCIP网络基础
  • 79.ScottPlot的MVVM实现 C#例子 WPF例子
  • PPT 相关资料介绍
  • 梧桐：开发者的命令行效率应用
  • TK矩阵：引领TikTok营销的新革命
  • 第R8周：RNN实现阿尔兹海默病诊断