小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

红黑树——学习总结以及封装map和set_map红黑树

作者：小丑西瓜9 | 2024-03-09 10:27:23

踩

map红黑树

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

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

最短路径：全黑
最长路径：一黑一红，黑红相间

上面这种树，AVL一定旋转，RB不一定旋转

旋转

约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

解决方方式：将p，u改为黑，g改为红，然后把g当成cur，继续向上调整

再向上调整即g改为黑

情况二：cur为红， p为红，g为黑，u不存在/u存在且为黑

情况三：cur为红(左p右边/右p左边)，p为红，g为黑，u不存在/u存在且为黑

和情况二完全类似，只是情况二是单旋，情况三是双旋

红黑树的实现

节点结构


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

红黑树中的节点和AVL相比就多了一个颜色_col ，只需要用两种状态表示即可，这里用枚举类型当作颜色

插入


template<class K, class T, class KeyOfT>
bool Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return 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 false;
            }
        }
 
        cur = new Node(data);
        if (kot(parent->_data) > kot(data))
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        cur->_parent = parent;
				
				//颜色变更以及旋转.....
		}

插入和AVL树插入一样，只不过是后续的旋转由平衡因子的修改变成了颜色的修改，且旋转规则不一样

template<class K, class T, class KeyOfT>

模版中的KeyOfT是为了以后同时实现set和map而做的仿函数，因为set是单个key值，而map是pair作key值，所以当map比较数据插入时，pair没有重载比较符> , < , >= , <= , == 所以当map插入值时，需要通过仿函数MapKeyOfT来传递first的值，依靠first的值来判断插入位置。而set只是为了配合map才会有仿函数SetKeyOfT


class map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };
		}
 
class set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
		}

此时可以通过定义KeyOfT kot; 来比大小kot(cur->_data) < kot(data) ，实现map时传入的则就是cur->_data->first < data->first

颜色变更以及旋转

分为前面说的三种情况

情况一：cur为红，p为红且在祖父节点左边，g为黑，**u存在且为红

将p，u改为黑，g改为红，然后把g当成cur，继续向上调整**


while (parent && parent->_col == RED)//当cur不是根节点或父节点的颜色是红时
        {
            Node* grandfather = parent->_parent;
            if (grandfather->_left == parent)
            {
                Node* uncle = grandfather->_right;
                // 情况1：u存在且为红，变色处理，并继续往上处理
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = BLACK;//p改黑
                    uncle->_col = BLACK;//u改黑
                    grandfather->_col = RED;//g改红
 
                    // 继续往上调整
                    cur = grandfather;//g当作c，继续调整
                    parent = cur->_parent;
                }

情况二：cur为红(左p左边)，p为红(g左)，g为黑，u不存在/u存在且为黑

情况三：cur为红(左p右边)，p为红(g左)，g为黑，u不存在/u存在且为黑


								//代码接上面
								else // 情况2+3：u不存在/u存在且为黑，旋转+变色
                {
                    //     g
                    //   p   u
                    // c
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        //      g
                        //   p     u
                        //     c
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        //parent->_col = RED;
                        grandfather->_col = RED;
                    }
 
                    break;
                }
            }

情况二：cur为红(右p右边)，p为红(g右)，g为黑，u不存在/u存在且为黑

情况三：cur为红(右p左边)，p为红(g右)，g为黑，u不存在/u存在且为黑


						//代码接上面
						else // (grandfather->_right == parent)
            {
                //    g
                //  u   p
                //        c
                Node* uncle = grandfather->_left;
                // 情况1：u存在且为红，变色处理，并继续往上处理
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
 
                    // 继续往上调整
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 情况2+3：u不存在/u存在且为黑，旋转+变色
                {
                    //    g
                    //  u   p
                    //        c
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else
                    {
                        //     g
                        //  u     p
                        //      c
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
 
                    break;
                }
            }
        }
				_root->_col = BLACK;
 
        return true;
    }

旋转——和AVL一样


		void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;
 
        Node* ppnode = parent->_parent;
 
        subR->_left = parent;
        parent->_parent = subR;
 
        if (ppnode == nullptr)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;
            }
 
            subR->_parent = ppnode;
        }
    }
 
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;
 
        Node* ppnode = parent->_parent;
 
        subL->_right = parent;
        parent->_parent = subL;
 
        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
    }

迭代器的实现

迭代器结构


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)
    {}
 
    // 1、typedef __RBTreeIterator<T, T&, T*> itertaor;  拷贝构造
    // 2、typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
    //  支持普通迭代器构造const迭代器的构造函数
 
    __RBTreeIterator(const __RBTreeIterator<T, T&, T*>& it)
            :_node(it._node)
    {}

红黑树的迭代器拷贝构造自身节点即可，然后再实现其他各种功能，如-> , * , != , ++ , -- 操作符号重载。

typedef __RBTreeIterator<T, T&, T*> itertaor; 使用迭代器时重命名它，把需要的参数传给模版，Ref为引用，Ptr为解引用，Self为迭代器。


		Ref operator*()//T&
    {
        return _node->_data;
    }
 
    Ptr operator->()
    {
        return &_node->_data;
    }//T*
 
    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }

迭代器遍历：++和--


Self& operator++()
    {
        if (_node->_right)
        {
            // 1、右不为空，下一个就是右子树的最左节点
            Node* subLeft = _node->_right;
            while (subLeft->_left)
            {
                subLeft = subLeft->_left;
            }
 
            _node = subLeft;
        }
        else
        {
            // 2、右为空，沿着到根的路径，找孩子是父亲左的那个祖先
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = parent->_parent;
            }
 
            _node = parent;
        }
 
        return *this;
    }

右不为空，下一个就是右子树的最左节点

右为空，沿着到根的路径，找孩子是父亲左的那个祖先。

自减的重载也是如此，把left换成right，right换成left即可


Self& operator--()
    {
        if (_node->_left)
        {
            // 1、左不为空，找左子树最右节点
            Node* subRight = _node->_left;
            while (subRight->_right)
            {
                subRight = subRight->_right;
            }
 
            _node = subRight;
        }
        else
        {
            // 2、左为空，孩子是父亲的右的那个祖先
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }
 
            _node = parent;
        }
 
        return *this;
    }

注意：这里返回的是Self迭代器类型，也就是对象类型，返回*this

基本的函数调用

begin和end


		itertaor begin()
    {
        Node* cur = _root;
        while (cur && cur->_left)//最左边就是begin
        {
            cur = cur->_left;
        }
 
        return itertaor(cur);//返回的迭代器类型要构造cur节点
    }
 
    itertaor end()
    {
        return itertaor(nullptr);
    }
 
    const_itertaor begin() const
    {
        Node* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }
 
        return const_itertaor(cur);//返回的迭代器类型要构造cur节点
    }
 
    const_itertaor end() const
    {
        return const_itertaor(nullptr);
    }

begin和end返回的都是迭代器类型，所以要调用迭代器的构造函数，支持普通迭代器构造const迭代器的构造函数，属于权限缩小。

判断平衡、高度、销毁

平衡


public:
		bool IsBalance()
    {
        if (_root && _root->_col == RED)
        {
            cout << "根节点颜色是红色" << endl;
            return false;
        }
 
        int benchmark = 0;//算出一条路上的黑节点个数
        Node* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++benchmark;
            cur = cur->_left;
        }
 
        // 连续红色节点
        return _Check(_root, 0, benchmark);
    }
 private:
		bool _Check(Node* root, int blackNum, int benchmark)
    {
        if (root == nullptr)
        {
            if (benchmark != blackNum)
            {
                cout << "某条路径黑色节点的数量不相等" << endl;
                return false;
            }
 
            return true;
        }
 
        if (root->_col == BLACK)
        {
            ++blackNum;
        }
 
        if (root->_col == RED
                && root->_parent
                && root->_parent->_col == RED)
        {
            cout << "存在连续的红色节点" << endl;
            return false;
        }
 
        return _Check(root->_left, blackNum, benchmark)
                && _Check(root->_right, blackNum, benchmark);
    }

高度


int _Height(Node* root)
    {
        if (root == NULL)
            return 0;
 
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
 
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

销毁


		~RBTree()
    {
        _Destroy(_root);
        _root = nullptr;
    }
private:
		void _Destroy(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
 
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }

封装set和map

map

对象结构


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

C++语言默认情况下，假定通过作用域运算符访问的名字不是类型，所以当我们要访问的是类型时候，必须显示的告诉编译器这是一个类型，通过关键字typename来实现这一点。 typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::itertaor iterator;
语句的真是面目是： typedef创建了存在类型的别名，而typename告诉编译器
RBTree<K, pair<const K, V>, MapKeyOfT>::itertaor 是一个类型而不是一个成员。

[ ]重载

begin和end的实现就不用说了，只需要返回_t.begin(); _t.end(); 即可。而[ ]重载是这样的：


V& operator[](const K& key)
    {
        pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
        return ret.first->second;
//first==iterator  first-> == _node->_data  first->second==_node->_data->second,也就是V值
        }

用一个pair<iterator,bool> 类型来接收插入后的返回结果，以便使用字典的方式插入值。

for (auto& e : map){ countMap[e]++; } 返回的countMap[e]值是_node->_data->second 也就是树中的V值。

我们前面Insert函数相应的也需要改变类型以及返回值


pair<itertaor, bool> Insert(const T& data)
{
	//已有data在，插入失败
	return make_pair(itertaor(cur), false);
	//要用newnode保存一下cur
	Node* newnode = cur;
	//data不在，插入成功
	return make_pair(itertaor(newnode), true);
}

然后调用即可


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

set

对象结构


template<class K>
    class set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:
        typedef typename RBTree<K, K, SetKeyOfT>::const_itertaor iterator;
        typedef typename RBTree<K, K, SetKeyOfT>::const_itertaor const_iterator;
		private:
				RBTree<K, K, SetKeyOfT> _t;

set和map相比只是少了[ ]重载，没什么好说的


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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/214715?site