C++ 红黑树封装map和set-EW帮帮网

前言

1.红黑树的改造

1.1主题框架

1.2迭代器

前言

map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。

在改造红黑树的时候，我们将会面对几个问题。

对红黑树的改造，关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是set的话，则是K，如果是map，则为pair<k,v>。如何用一个节点结构控制两种类型，使用类模板参数T

在插入的过程中，因为是泛型编程，需要用红黑树给map和set套一个“壳子”，在比较大小的过程中，pair的比较是通过first和second共同决定的，因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key数据

关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。

红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。

1.红黑树的改造

1.1主题框架

(1) K 是给find，erase用的，T 是给节点，insert用的；

(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。

红黑树的结点构造

using namespace std;
enum color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* left;
	RBTreeNode<T>* right;
	RBTreeNode<T>* _parent;

	T data;

	color col;

	RBTreeNode(const T& data)
		:left(nullptr)
		, right(nullptr)
		, _parent(nullptr)
		, data(data)
		, col(RED)
	{}
};

主体框架

class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator; //迭代器
	typedef __TreeIterator<T, const T&, const T*> const_iterator; //const迭代器
          


       .......//相应的接口
private:	
    Node* root = nullptr;
};

1.2迭代器

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

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

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

operator++ （）

这里需要重点提的是operator++

它与以往的容器不相同，这是通过二叉树构建，根据它的中序遍历实现++

为了完成二叉树的中序遍历，我们需要从局部的某一过程考虑，就是假设 it 已经走到了某一节点，要找到下一个访问的节点，分为两种情况：

1.当前节点的右子树不为空

当结点是it的时候，说明左子树已经全部访问完了，开始访问右子树，右子树不为空，我们下一个访问的节点是15，所以要找到右子树的最左节点。

2. 当前节点的右子树为空：

当it为该节点时，右子树为空，访问的下一个节点时8，因为it被访问完时，代表着根节点已经访问完了，要找祖先作为祖先父亲的左节点即可。

begin（）和end（）

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 const_iterator(cur);
}
const_iterator end()const
{	
	return const_iterator(nullptr);
}

1.3红黑树相关接口的改造

Find函数的改造

查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。

Iterator Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data > key)
			cur = cur->_left;
		else if (cur->_data < key)
			cur = cur->_right;
		else
			return Iterator(cur);
	}
	return End();
}

Insert 函数的改造

map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator, bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		return make_pair(Iterator(_root), true);
	}

	KeyOfT kot;  仿函数对象
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return make_pair(Iterator(cur), false);
	}
	cur = new Node(data);
	Node* newnode = cur;

 	//此处省略变色+旋转部分的代码……

剩下的变色或旋转代码上一篇讲到过

红黑树

2.红黑树改造的完整代码

#include <iostream>
#include <assert.h>
using namespace std;

//枚举颜色
enum Colour
{
	RED,
	BLACK
};

//节点类
template <class T>
struct RBTreeNode
{
	T _data;

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair<K, V> _kv;
	Colour _col;

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

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

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

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

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

	//从局部的某一个过程考虑
	Self& operator++()
	{
		if (_node->_right)
		{
			//右不为空，右子树的最左节点就是下一个访问的节点
			Node* leftMost = _node->_right;
			while (leftMost->_left)
				leftMost = leftMost->_left;

			_node = leftMost;
		}
		else
		{
			//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先
			//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点

			Node* cur = _node;
			Node* parent = cur->_parent;
			//循环找祖先
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};


//K 是给find，erase用的，T 是给节点，插入用的
// KeyOfT 是由于下面需要比较，但是比较时不知道T的类型，
// set是key类型的比较，map是pair类型的比较，要统一变成key的比较

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;


	//中序遍历，找树的最左节点
	Iterator Begin()
	{
		//Node* cur = _root;
		Node* leftMost = _root;

		while (leftMost->_left)
			leftMost = leftMost->_left;

		return Iterator(leftMost);
	}

	Iterator End()
	{
		return Iterator(nullptr);
	}

	ConstIterator Begin()const
	{
		//Node* cur = _root;
		Node* leftMost = _root;

		while (leftMost->_left)
			leftMost = leftMost->_left;

		return ConstIterator(leftMost);
	}

	ConstIterator End()const
	{
		return ConstIterator(nullptr);
	}

	Iterator Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data > key)
				cur = cur->_left;
			else if (cur->_data < key)
				cur = cur->_right;
			else
				return Iterator(cur);
		}
		return End();
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			return make_pair(Iterator(_root), true);
		}

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

		//新增节点，颜色为红色
		cur->_col = RED;
		
				if (kot(parent->data) < kot(data))
		{
			parent->right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->left = cur;
			cur->_parent = parent;
		}
		while (parent && parent->col == RED)
		{
			Node* grandparent = parent->_parent;
			if (parent == grandparent->left)
			{
				Node* uncle = grandparent->right;
				if (uncle && uncle->col == RED)
				{
					parent->col = uncle->col = BLACK;
					if (grandparent == root)
					{
						grandparent->col = BLACK;
						return make_pair(root, true);
					}
					else
					{
						grandparent->col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
				}
				else
				{
					if (cur = parent->left)
					{
						RotateR(grandparent);
						parent->col = RED;
						grandparent->col = BLACK;
					}
					else
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->col = BLACK;
						grandparent->col = RED;
					}
					break;
				}
			}
			else//parent=grandparent->right
			{
				Node* uncle = grandparent->left;
				if (uncle && uncle->col == RED)
				{
					parent->col = uncle->col = BLACK;
					if (grandparent == root)
					{
						grandparent->col = BLACK;
						return make_pair(root, true);
					}
					else
					{
						grandparent->col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
				}
				else
				{
					if (cur == parent->right)
					{
						RotateL(grandparent);
						parent->col = BLACK;
						grandparent->col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->col = BLACK;
						grandparent->col = RED;
					}
					break;
				}
			}
		}

	}
	root->col = BLACK;
	return make_pair(newnode, true);
}
		
private:
        void RotateL(Node* parent)
{
	Node* subR = parent->right;
	Node* subRL = subR->left;

	subR->left = parent;
	parent->right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	Node* parentParent = parent->_parent;
	parent->_parent = subR;
	if (parent == root)
	{
		root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->left == parent)
		{
			parentParent->left = subR;
		}
		else
		{
			parentParent->right = subR;
		}
		subR->_parent = parentParent;
	}

}
void RotateR(Node* parent)
{
	Node* subL = parent->left;
	Node* subLR = parent->right;

	parent->left = subLR;
	subL->right = parent;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	Node* parentParent = parent->_parent;
	parent->_parent = subL;
	if (root == parent)
	{
		root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parentParent->left == parent)
		{
			parentParent->left = subL;
		}
		else
		{
			parentParent->right = subL;
		}
		subL->_parent = parentParent;
	}
}    
		Node* _root = nullptr;

};

3.Set的封装

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。

为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可

namespace bit
{
	template<class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		
		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;
	};
}
void Print(const cc::set<int>& s)
{
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

//测试代码
void Test_set()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 16,3,7,11,9,26,18,14,15 };
	cc::set<int> s;

		for (auto e : a)
			s.insert(e);

		for (auto e : s)
			cout << e << " ";

		cout << endl;

		Print(s);
}

4.Map的封装

#include "RBTree.h"

namespace cc
{
	template<class K, class V>
	class map
	{
		//获取 pair 中的 key
		struct MapOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapOfT>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapOfT>::ConstIterator const_iterator;


		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin()const
		{
			return _t.Begin();
		}

		const_iterator end()const
		{
			return _t.End();
		}

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

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

		//给一个key，返回value的引用
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K,V>, MapOfT> _t;
	};
}


//测试代码
void Test_map()
{
	cc::map<string, string> dict;

	dict.insert({ "left","左边" });
	dict.insert({ "right","右边" });
	dict.insert({ "insert","插入" });

	dict["left"] = "剩余，左边";

	cc::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//it->first += 'x'; //err
		it->second += 'y'; //ok

		cout << it->first << ":" << it->second << endl;
		++it;
	}

	cout << endl;
}

C++ 红黑树封装map和set

前言

1.红黑树的改造

1.1主题框架

1.2迭代器

operator++ （）

begin（）和end（）

1.3红黑树相关接口的改造

Find函数的改造

Insert 函数的改造

2.红黑树改造的完整代码

3.Set的封装

4.Map的封装

网站公告

今日签到

热门文章

最新发布