C++精通之路：红黑树迭代器的模拟实现和讲解

雪芙花

发布于 2022-10-31 18:16:22

4390

发布于 2022-10-31 18:16:22

文章被收录于专栏：雪芙花雪芙花

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第8天，点击查看活动详情

一：红黑树的迭代器

需要注意的是：

迭代器本质上是指针的一个封装的类，其底层就是指针；好处是可以方便遍历，是数据结构的底层实现与用户透明
对于string,vector,list等容器，其本身的结构上是比较简单的，迭代器的实现也很简单；但是对于二叉树结构的红黑树来说需要考虑很多的问题

1.begin()与end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间
对红黑树进行中序遍历后，可以得到一个有序的序列，因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置即nullptr

如图：

2.operator++()与operator--()

++逻辑的实现：

因为红黑树的中序是有序的，所以++是找到该节点在中序中的下一个节点
因为中序是左中右，所以我们可以分为右子树存在和不存在来讨论下一个节点是谁
当右子树存在时，右子树的最左节点即是下一个节点
当右子树不存在时，我们需要向上寻找，因为中序是左中右的，所以该子树已经被遍历完了，则++操作后应该在该结点的祖先结点中找到孩子不在父亲右的祖先

--的逻辑是一样的

代码实现：

operator++()

Self&amp; operator++()
{
    if (_node->_right)//右子节点存在
    {
        //找到右子树中最左节点
        Node* cur = _node->_right;
        while (cur->_left)
        {
            cur = cur->_left;
        }
        _node = cur;
    }
    else//右子节点不存在，向上找
    {
        Node* cur = _node;//记录走过的节点
        Node* parent = _node->_parent;
        while (parent &amp;&amp; parent->_right == cur)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    return *this;
}

operator--()：

Self&amp; operator--()
{
    if (_node->_left)//左子节点存在
    {
        //找左子树中的最右节点
        Node* cur = _node->_left;
        while (cur->_right)
        {
            cur = cur->_right;
        }
        _node = cur;
    }
    else//左子节点不存在
    {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent &amp;&amp; parent->_left == cur)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    return *this;
}

反向迭代器适配器

因为反向迭代器与正向迭代器在原理实现中是相同的，只是方向反了而已所以我们可以用正向迭代器来封装出反向迭代器，在正向迭代器的基础上，对其接口进行封装达到反向迭代器的效果

正向迭代器实现代码：

template<class T, class Ref, class Ptr>
struct _TreeIterator
{
    //声明类型，便于反向迭代器对类型的提取
    typedef Ref reference;
    typedef Ptr pointer;
    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 &amp;_node->_data;
    }

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

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

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

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

        return *this;
    }
};

反向迭代器实现代码：

//适配器构造反向迭代器
template<class Iterator>
struct ReverseIterator
{
    //类型未实例化，无法取出里面的类型，此时需要使用typename：告诉编译器等实例化后再到类里面找对应的类型
    typedef typename Iterator::reference Ref;
    typedef typename Iterator::pointer Ptr;
    typedef ReverseIterator<Iterator> Self;

    Iterator _it;

    ReverseIterator(Iterator it)
        :_it(it)
    {}
    
    //在正向迭代器接口上进行封装复用   
    Ref operator*()
    {
        return *_it;
    }

    Ptr operator->()
    {
        return _it.operator->();
    }

    bool operator==(const Self&amp; it)const
    {
        return it._it==_it;
    }

    bool operator!= (const Self&amp; it)const//两个const
    {
        return _it != it._it;
    }

    Self&amp; operator++()
    {
        --_it;
        return *this;
    }

    Self&amp; operator--()
    {
        ++_it;
        return *this;
    }
};

二：改造红黑树

因为set是K模型的容器，而map是KV模型的容器.所以要用红黑树来模拟实现这两个容器，需要添加一些东西使得其能适配两者，添加和改变的东西如下：

1. 节点的改变：

对于红黑树的节点我们需要节点对于set来说储存key，对于map来说储存key-value键值对，所以这里我们就直接让节点类型的阈值类型为T，用来控制储存类型

代码的实现：

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

    T _data;//T可以是key也可以是pair<K,V>
    Colour _col;

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

2. 主体的改变

template<class K, class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    //.......
private:
    Node* _root;
};

K是用来比较的类型，T是用来存储的类型

这里就体现了对map和set的兼容。
当为map时，传进来的T为pirpair<key,value>
当为set时，传进来的T为K
达到了存储不同数据类型的目的

3. 添加仿函数来适配数据间的比较

在删除添加时，我们要进行节点中数据的比较，当为map时，pirpair<key,value>与Kl类型无法比较时，这里就需要仿函数来帮助我们适配

对于不同容器我们需要不同的仿函数类型，由此在红黑树的模板列表中还需要一个模板类型参数，灵活控制传入的仿函数类型

仿函数的本质是创造一个类，通过operator（）的重载来实现的，与函数重载类似，但在模板内，就只能使用仿函数来实现了。

红黑树框架：

template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    //...
private:
    Node* _root;
};

map实现框架：

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

set实现框架：

namespace cole
{
    template<class K>
    class set
    {
        struct SetOfKey
        {
            const K&amp; operator()(const K&amp; key)
            {
                return key;
            }
        };
    public:
        //...
    private:
        RBTree<K, K, SetOfKey> _t;
    };
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-10-06，如有侵权请联系 cloudcommunity@tencent.com 删除

java