用红黑树模拟实现map和set

今天我们用红黑树来模拟实现map和set，我们可以参考STL源码，不用自己造轮子。一下是STL源码中的片段，它定义节点的颜色是用const的全局变量，同样需要三个指针left,right,parent.还用了一个继承，我也不知道大佬当时是怎么想的，其实不用继承也是一样可以搞，那么我们模拟实现就不搞继承了。大佬当时可能是出于某种原因吧。

typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;

struct __rb_tree_node_base
{ 
 typedef __rb_tree_color_type color_type;
  typedef __rb_tree_node_base* base_ptr;

  color_type color; 
  base_ptr parent;
  base_ptr left;
  base_ptr right;

  static base_ptr minimum(base_ptr x)
  {
    while (x->left != 0) x = x->left;
    return x;
  }

  static base_ptr maximum(base_ptr x)
  {
    while (x->right != 0) x = x->right;
    return x;
  }
};

template 
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node* link_type;
  Value value_field;
};

我们定义接定义节点的代码如下：

enum Colour
	{
		RED=0,
		BALCK=1
	};

	//定义节点
	template
	class RBTreeNode
	{
	public:
		RBTreeNode(const T& data)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(RED)
			,_data(data)
		{

		}
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		Colour _col;
		T _data;
	};
template   //迭代器
	class RBTreeIterator
	{
	public:
		typedef RBTreeNode Node;
		typedef RBTreeIterator  Self;
		RBTreeIterator(Node* node)
			:_node(node)
		{

		}
    }；

class RBTree
	{
	public:
		typedef RBTreeNode Node;
		typedef RBTreeIterator iterator;
		typedef RBTreeIterator< T, const T&, const T*> const_iterator;
		RBTree()
			:_root(nullptr)
		{

		}
}；

这些没啥好说的的，但是map和set在STL源码库中用的是一颗红黑树，但是set是k模型，map是K,V模型，那么我们先看一下大佬是怎么设置的。

可以看出set和map一个传递的是key一个传递的pair，那红黑树怎么识别的，红黑树第三个模板参数可以将传递过来的参数取出来，在STL中仿函数的作用就体现出来了。要不然怎么说仿函数是STL六大组件之一呢。所以在set中我们就可以定义仿函数的使用方法：代码如下：

#include"stl_tree.h"


namespace bit
{
	template
	class set
	{
	public:
		class SetofT
		{
		public:
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree::iterator iterator;

		std::pair insert(const K& key)
		{
			return _rb.insert(key);
		}
		iterator begin()
		{
			return _rb.begin();
		}
		iterator end()
		{
			return _rb.end();
		}

	private:
		RBTree _rb;
	};
	void set_test()
	{
		set s;
		s.insert(1);
		s.insert(4);
		s.insert(2);
		s.insert(24);
		s.insert(2);
		s.insert(12);
		s.insert(6);

		set::iterator it = s.begin();
		while (it != s.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;

		for (auto e : s)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		set copy(s);
		for (auto e : copy)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		set ss;
		ss.insert(111);
		ss.insert(422);

		copy = ss;
		for (auto e : copy)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}
}

在map中仿函数的定义如下：

#include"stl_tree.h"


namespace bit
{
	template
	class map
	{
	public:
		class MapOfT
		{
		public:
			const K&  operator()(const std::pair& kv)
			{
				return kv.first;
			}
		};
		typedef typename RBTree, MapOfT>::iterator iterator;

		iterator begin()
		{
			return _rb.begin();
		}
		iterator end()
		{
			return _rb.end();
		}
		std::pair insert(const std::pair& kv)
		{
			return _rb.insert(kv);
		}

		V& operator[](const K& key)
		{
			auto ret = _rb.insert(std::make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree, MapOfT> _rb;
	};
	void test_map()
	{
		map dict;
		dict.insert(std::make_pair("sort", "排序"));
		dict.insert(std::make_pair("string", "字符串"));
		dict.insert(std::make_pair("map", "地图"));
		dict["left"];
		dict["left"] = "剩余";
		dict["map"] = "地图/容器";

		auto it = dict.begin();
		while (it != dict.end())
		{
			std::cout << it->first << ":" << it->second << std::endl;
			++it;
		}
		std::cout << std::endl;
	}
}

typedef typename RBTree, MapOfT>::iterator iterator;这句代码很重要，如果不加typename会编译报错，没有办法实例化，加了可以告诉编译器先去推导，等实例化之后在去执行。下面我们来看看红黑树的迭代器的实现代码如下：

//红黑树迭代器
	template
	class RBTreeIterator
	{
	public:
		typedef RBTreeNode Node;
		typedef RBTreeIterator  Self;
		RBTreeIterator(Node* node)
			:_node(node)
		{

		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		Self& operator++()
		{
			if (_node->_right)
			{
				Node* min = _node->_right;
				while (min != nullptr && min->_left != nullptr)
				{
					min = min->_left;
				}
				_node = min;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent != nullptr && cur == parent->_right)
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		Self& operator--()
		{
			if (_node->_left)
			{
				Node* max = _node->_left;
				while (max->_right != nullptr)
				{
					max = max->_right;
				}
				_node = max;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent != nullptr && 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;
		}

	private:
		Node* _node;
	};

迭起器的++和--：

对红黑树的改造，只需要把比较的时候用set,map各自的仿函数，进行比较即可。

std::pair insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_col = BALCK;
				return std::make_pair(iterator(_root), true);
			}
			Node* parent = nullptr;
			Node* cur = _root;
			KeyOfT kot;      //定义仿函数对象
			while (cur != nullptr)
			{
				if (kot(data) > kot(cur->_data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(data) < kot(cur->_data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return std::make_pair(iterator(cur), false);
				}
			}
			//申请节点
			cur = new Node(data);
			Node* newnode = cur;
			cur->_col = RED;
			if (kot(data) > kot(parent->_data))
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
}

红黑树全部代码如下： stl_tree.h

#pragma once
#include
namespace bit
{
	enum Colour
	{
		RED=0,
		BALCK=1
	};

	//定义节点
	template
	class RBTreeNode
	{
	public:
		RBTreeNode(const T& data)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(RED)
			,_data(data)
		{

		}
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		Colour _col;
		T _data;
	};


	//红黑树迭代器
	template
	class RBTreeIterator
	{
	public:
		typedef RBTreeNode Node;
		typedef RBTreeIterator  Self;
		RBTreeIterator(Node* node)
			:_node(node)
		{

		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		Self& operator++()
		{
			if (_node->_right)
			{
				Node* min = _node->_right;
				while (min != nullptr && min->_left != nullptr)
				{
					min = min->_left;
				}
				_node = min;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent != nullptr && cur == parent->_right)
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		Self& operator--()
		{
			if (_node->_left)
			{
				Node* max = _node->_left;
				while (max->_right != nullptr)
				{
					max = max->_right;
				}
				_node = max;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent != nullptr && 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;
		}

	private:
		Node* _node;
	};

	//红黑树
	template   //第三个模板参数为仿函数
	class RBTree
	{
	public:
		typedef RBTreeNode Node;
		typedef RBTreeIterator iterator;
		typedef RBTreeIterator< T, const T&, const T*> const_iterator;
		RBTree()
			:_root(nullptr)
		{

		}
		RBTree(const RBTree& s)
		{
			_root = Copy(s._root);
		}
		RBTree& operator=(RBTree s)
		{
			std::swap(_root, s._root);
			return *this;
		}
		~RBTree()
		{
			Destroy(_root);
		}
		iterator begin()
		{
			Node* min = _root;
			while (min != nullptr && min->_left != nullptr)
			{
				min = min->_left;
			}
			return iterator(min);
		}
		iterator end()
		{
			return iterator(nullptr);
		}
		iterator find(const K& key)
		{
			Node* cur = _root;
			if (key > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else if (key < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else
			{
				return iterator(cur);
			}
		}
		std::pair insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_col = BALCK;
				return std::make_pair(iterator(_root), true);
			}
			Node* parent = nullptr;
			Node* cur = _root;
			KeyOfT kot;
			while (cur != nullptr)
			{
				if (kot(data) > kot(cur->_data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(data) < kot(cur->_data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return std::make_pair(iterator(cur), false);
				}
			}
			//申请节点
			cur = new Node(data);
			Node* newnode = cur;
			cur->_col = RED;
			if (kot(data) > kot(parent->_data))
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_left = cur;
				cur->_parent = parent;
			}

			//控制平衡
			while (parent != nullptr && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right;
					//情况1:uncle存在且为红
					if (uncle != nullptr && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BALCK;
						grandfather->_col = RED;
						
						//继续向上更新
						cur = grandfather;
						parent = cur->_parent;
					}
					//情况2：uncle不存在/存在且为黑，旋转
					else
					{
						if (cur == parent->_left) //右单旋
						{
							RotateR(grandfather);
							grandfather->_col = RED;
							parent->_col = BALCK;
						}
						else    //左右双旋
						{
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BALCK;
							grandfather->_col = RED;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandfather->_left;
					//情况1:uncle存在且为红
					if (uncle != nullptr && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BALCK;
						grandfather->_col = RED;

						//继续向上更新
						cur = grandfather;
						parent = cur->_parent;
					}
					else//情况2：uncle不存在/存在且为黑，旋转
					{
						if (cur == parent->_right)  //左单旋
						{
							RotateL(grandfather);
							grandfather->_col = RED;
							parent->_col = BALCK;
						}
						else   //右左双旋
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BALCK;
							grandfather->_col = RED;
						}
					}
					break;
				}
			}
			_root->_col = BALCK;
			return std::make_pair(iterator(newnode), true);
		}
	private:
		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			Node* parentparent = parent->_parent;

			parent->_left = subLR;
			if (subLR != nullptr)
				subLR->_parent = parent;

			subL->_right = 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;    //维护三叉链
			}
		}
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			Node* parentparent = parent->_parent;

			parent->_right = subRL;
			if (subRL != nullptr)
				subRL->_parent = parent;

			subR->_left = parent;
			parent->_parent = subR;
			if (_root == parent)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parentparent->_left == parent)
					parentparent->_left = subR;
				else
					parentparent->_right = subR;
				subR->_parent = parentparent;  //维护三叉链
			}
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->_data);
			newnode->_col = root->_col;
			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			if (newnode->_left != nullptr)
				newnode->_left->_parent = newnode;

			if (newnode->_right != nullptr)
				newnode->_right->_parent = newnode;
			return newnode;1
		}
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}
	private:
		Node* _root;
	};
}

细节主要是在旋转的细节上，其他的都是在红黑树的基础上进行封装。 set.h

#include"stl_tree.h"

namespace bit
{
	template
	class set
	{
	public:
		struct SetOfT
		{

			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
			typedef typename RBTree::iterator iterator;
			std::pair insert(const K& key)
			{
				return _rb.insert(key);
			}
			iterator begin()
			{
				return _rb.begin();
			}
			iterator end()
			{
				return _rb.end();
			}
			iterator find(const K& key)
			{
				return _rb.find(key);
			}
	private:
		RBTree _rb;
	};
	void test_set()
	{
		set s;
		s.insert(1);
		s.insert(4);
		s.insert(2);
		s.insert(24);
		s.insert(2);
		s.insert(12);
		s.insert(6);

		set::iterator it = s.begin();
		while (it != s.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;

		for (auto e : s)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		set copy(s);
		for (auto e : copy)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		set ss;
		ss.insert(111);
		ss.insert(422);

		copy = ss;
		for (auto e : copy)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}
}

map.h

#include"stl_tree.h"


namespace bit
{
	template
	class map
	{
	public:
		class MapOfT
		{
		public:
			const K&  operator()(const std::pair& kv)
			{
				return kv.first;
			}
		};
		typedef typename RBTree, MapOfT>::iterator iterator;

		iterator begin()
		{
			return _rb.begin();
		}
		iterator end()
		{
			return _rb.end();
		}
		std::pair insert(const std::pair& kv)
		{
			return _rb.insert(kv);
		}

		V& operator[](const K& key)
		{
			auto ret = _rb.insert(std::make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree, MapOfT> _rb;
	};
	void test_map()
	{
		map dict;
		dict.insert(std::make_pair("sort", "排序"));
		dict.insert(std::make_pair("string", "字符串"));
		dict.insert(std::make_pair("map", "地图"));
		dict["left"];
		dict["left"] = "剩余";
		dict["map"] = "地图/容器";

		auto it = dict.begin();
		while (it != dict.end())
		{
			std::cout << it->first << ":" << it->second << std::endl;
			++it;
		}
		std::cout << std::endl;
	}
}

test.cpp

#include"set.h"
#include"map.h"


int main()
{
	//bit::set_test();
	bit::test_map();
}

这几节可能难度比较大，但是多理理思路根据思路多写代码，小编AVL树和红黑树的代码写了不下10遍，架子也是理了很多遍，这个还是小编大二学的，很多年不写仍然会忘记，但是思路还在，理一理就比较清晰了。但是后面项目的难度至少是红黑树这节难度的3倍。加油XDM。

用红黑树模拟实现map和set

C/C++/C#相关栏目本月热门文章