c++利用红黑树实现map和set

• 1. 红黑树的封装
• • 1.1 定义红黑树节点
  • 1.2 定义迭代器
  • 1.3 红黑树改写
• 2. map和set的封装
• • 2.1 map.h
  • 2.2 set.h
• 3. 测试程序

#pragma once
#include 

enum Colour {
	Red,
	Black,
};

template
struct RBNode {
	RBNode* _left;
	RBNode* _right;
	RBNode* _parent;

	Value _kv;
	Colour _colour;
	
	RBNode(const Value& kv = Value())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
	{}
};

template   
struct RBTree_iterator
{
	//typedef RBTree_iterator     iterator;
	//typedef RBTree_iterator const_iterator;
	typedef RBTree_iterator   self;
	typedef RBNode Node;

	Node* _node;

	RBTree_iterator() {}
	RBTree_iterator(Node* x) 
		:_node(x)
	{}

	//RBTree_iterator(const iterator& it) 
	//	:_node(it._node)
	//{}

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

	Ptr operator->() const { return &(operator*()); }


	self& operator++() 
	{ 
		if (_node->_right)
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else
		{
			Node* parent = _node->_parent;
             //中序 左->中->右，当访问的节点在父亲的右边，说明父亲已经被访问了，应该访问父亲的父亲。
			while (_node == parent->_right) 
			{
				_node = parent;
				parent = parent->_parent;
			}
			if(_node->_right != parent )
				_node = parent;
		}
		return *this;
	}

	//self& operator--()   //右->中->左
	//{ 
	//	if (_node->_left)  //访问左边节点的最右节点
	//	{
	//		_node = _node->_left;
	//		while (_node->_right)
	//		{
	//			_node = _node->_right;
	//		}
	//	}
	//	else //左边节点不存在，访问当前节点的父亲
	//	{
	//		Node* parent = _node->_parent;
	//		while (parent && _node == parent->_left)  
	//		{
	//			_node = parent;
	//			parent = parent->_parent;
	//		}
	//		_node = parent;
	//	}
	//	return *this;
	//}

	//为了重载operator++， 将end()定义了header，实际上的end()应为_header->right
	//定义header的作用在这儿体现

	//另外要注意的是， 这个operator--无法被用户调用，应为会打印出_header->_kv,而且end()为leftmost的最后节点无法访问
	//它的作用可以用来封装反向迭代器。
	self operator--() 
	{
		if (_node->_colour == Red && _node->_parent->_parent == _node) //为header节点
		{
			_node = _node->_right;
		}
		else if (_node->_left)  //左不为空
		{
			Node* min_node = _node->_left;
			while (min_node->_right)
			{
				min_node = min_node->_right;
			}
			_node = min_node;
		}
		else
		{
			Node* parent = _node->_parent;
			while (_node == parent->_left)
			{
				_node = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

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

// Value：对于 set来说是key类型，对于map是pair；KeyOfValue：用来取出map和set中的key，是个仿函数
template  
class RBTree 
{
	typedef RBNode Node;
private:
	Node* LeftMost() const
	{
		Node* leftmost = _header->_left;

		return leftmost;
	}

	Node* RightMost() const
	{
		Node* rightmost = _header->_right;

		return rightmost;
	}
public:
	typedef RBTree_iterator const_iterator;

	const_iterator begin() const
	{
		return const_iterator(LeftMost());
	}

	const_iterator end() const
	{
		return const_iterator(_header);
	}


public:
	RBTree()
		:_root(nullptr)
	{
		_header = new Node;
		_header->_colour = Red;  //将header的颜色设为红色，用来标记
	}

	bool _RBtree_Insert(const Value& kv)
	{
		Node* newnode = new Node(kv);
		if (_header->_parent == nullptr)
		{
			_root = newnode;

			_header->_parent = _root;
			_root->_parent = _header;

			_header->_left = _root;
			_header->_right = _root;
			_root->_colour = Black;

			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur) // 找插入的位置
		{
			//if (cur->_kv.first > kv.first)
			 //使用KeyOfValue()构造的仿函数匿名对象去除key值，将cur的key值和插入的节点key进行比较
			if(KeyOfValue()(cur->_kv) > KeyOfValue()(kv)) 
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (KeyOfValue()(cur->_kv) < KeyOfValue()(kv))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;  //找不到返回，找到了执行插入操作；等于的情况有冗余，不执行插入
			}
		}

		cur = newnode;
		cur->_colour = Red; //插入红色的节点

		//if (parent->_kv.first > kv.first)
		if(KeyOfValue()(parent->_kv) > KeyOfValue()(kv))
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		else  //不存在等于情况，等于上面已经返回了
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		// 调整部分
		while (parent && parent->_colour == Red) //父节点存在且为红，有连续的红节点，继续向上调整
		{
			Node* grandparent = parent->_parent;
			if (grandparent->_left == parent)  // 先考虑父节点在左的情况
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_colour == Red)  //叔叔存在且为红，继续向上调整。
				{
					parent->_colour = Black;
					uncle->_colour = Black;
					grandparent->_colour = Red;
				}
				else //叔叔存在且为黑 或者 叔叔不存在
				{
					if (cur == parent->_left) //cur、parent、grandparent三个节点在一条直线上，右单旋
					{
						RotateR(grandparent);
						grandparent->_colour = Red;
						parent->_colour = Black;
					}
                    // cur、parent、grandparent三个节点在折直线上，先以parent进行左单旋，然后以grandparent进行右单旋
					else 
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_colour = Black;
						grandparent->_colour = Red;
					}
					break; //调整后
				}
			}
			else  //父节点在grandparent的右
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_colour == Red)  //叔叔存在且为红，继续向上调整。
				{
					parent->_colour = Black;
					uncle->_colour = Black;
					grandparent->_colour = Red;
				}
				else //叔叔存在且为黑 或者 叔叔不存在
				{
					if (cur == parent->_right) //cur、parent、grandparent三个节点在一条直线上，左单旋
					{
						RotateL(grandparent);
						grandparent->_colour = Red;
						parent->_colour = Black;
					}
                    // cur、parent、grandparent三个节点在折直线上，先以parent进行右单旋，然后以grandparent进行左单旋
					else 
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_colour = Black;
						grandparent->_colour = Red;
					}
					break; 
				}
			}
		}
		//**************** 更新_header ***************
		Node* leftmost = _root;
		while (leftmost && leftmost->_left)
		{
			leftmost = leftmost->_left;
		}
		_header->_left = leftmost;

		Node* rightmost = _root;
		while (rightmost && rightmost->_right)
		{
			rightmost = rightmost->_right;
		}
		_header->_right = rightmost;

		_root->_parent = _header;  //注意调整root，因为旋转后root可能发生了变化
		_header->_parent = _root;
		//********************************************
		_root->_colour = Black;  //将根节点置黑
		return true;
	}

	void RotateR(Node* parent)
	{
		Node* pleft = parent->_left;
		Node* pleftR = pleft->_right;
		Node* parentParent = parent->_parent;

		parent->_parent = pleft;
		pleft->_right = parent;

		if (pleftR) //Pleft_Right若为nullptr，则无法找到其parent
		{
			pleftR->_parent = parent;
		}
		parent->_left = pleftR;

		if (parent == _root) //若原来的parent为根，则将pleft更新为根节点
		{
			_root = pleft;
			_root->_parent = nullptr;
		}
		else // parent不为根节点，则其存在父节点，将pleft的父节点与原来parent的父节点进行链接
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = pleft;
			}
			else
				parentParent->_right = pleft;
			pleft->_parent = parentParent;
		}
	}
	
	void RotateL(Node* parent)
	{
		Node* pright = parent->_right;
		Node* prightL = pright->_left;
		Node* parentParent = parent->_parent;

		parent->_parent = pright;
		pright->_left = parent;

		if (prightL)
		{
			prightL->_parent = parent;
		}
		parent->_right = prightL;

		if (parent == _root)
		{
			_root = pright;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = pright;
			}
			else if (parentParent->_right == parent)
			{
				parentParent->_right = pright;
			}
			pright->_parent = parentParent;
		}
	}
	Node* returenROOT()
	{
		return _header->_parent;
	}

private:
	Node* _root;
	Node* _header;
};

#pragma once

#include "RBTree.h"

template 
class map
{
public:
	typedef Key key_type;
	typedef std::pair value_type;

	//typedef RBTree rep_type;
	//typedef tpedname rep_type::const_iterator iterator;

private:
	struct KeyOfValueFunc   //定义一个仿函数，取出红黑树的key值
	{
		const key_type& operator()(const value_type& k) const
		{
			return k.first;
		}
	};
	typedef RBTree  RBTreeType;
	RBTreeType _t;

public:
	typedef typename RBTree::const_iterator iterator;

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

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

public:
	bool insert(const value_type& kv)
	{
		return _t._RBtree_Insert(kv);
	}
};

#pragma once

#include "RBTree.h"

template 
class set
{
public:
	typedef Key key_type;
	typedef Key value_type;

private:
	struct KeyOfValueFunc   //定义一个仿函数，取出红黑树的key值
	{
		const key_type& operator()(const key_type& k) const
		{
			return k;
		}
	};
	typedef RBTree  RBTreeType;
	RBTreeType _t;  //set的成员变量是一棵红黑树

public:

	typedef typename RBTree::const_iterator iterator;

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

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

public:
	bool insert(const Key& key)
	{
		return _t._RBtree_Insert(key);
	}

	typedef RBNode Node;

	Node* returenROOT()
	{
		return _t.returenROOT();
	}
};

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include "set.h"
#include "map.h"

void PrintSingleNode(FILE* pFile, RBNode* root)
{
	if (root->_colour == Black)
	{
		fprintf(pFile, "tnode[shape=record,style="rounded, filled",color=black,fontcolor=white, weight = 20];n");
	}
	else
	{
		fprintf(pFile, "tnode[shape=record,style="rounded, filled",color=red,fontcolor=white,  weight = 20];n");
	}
	fprintf(pFile, "t%d[label=" |  %d |  ", labelfontsize = 20];n", root->_kv, root->_kv);
}

void WriteTree2File(FILE* pFile, RBNode* root, RBNode* Header)
{
	
	if (nullptr == root) return;
	if (root->_parent == Header)
	{
		PrintSingleNode(pFile, root);
	}

	if (root->_left != nullptr)
	{
		PrintSingleNode(pFile, root->_left);
		fprintf(pFile, "t%d:f0:sw->%d:f1;n", root->_kv, root->_left->_kv);
	}
	if (root->_right != nullptr)
	{
		PrintSingleNode(pFile, root->_right);
		fprintf(pFile, "t%d:f2:se->%d:f1;n", root->_kv, root->_right->_kv);
	}
	WriteTree2File(pFile, root->_left, Header);
	WriteTree2File(pFile, root->_right, Header);
}


int main()
{
	set t;
	map m;
	int a[] = { 20,30,35,14,26, 24 ,28, 22 ,36,32};
	for (auto e : a)
	{
		t.insert(e);
		m.insert(std::make_pair(e, e*e));
	}

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

	std::cout << std::endl;

	std::cout << "Test For My map!" << std::endl;

	map::iterator itm = m.begin();
	while (itm != m.end())
	{
		std::cout << itm->first << "->" << itm->second << " ";
		++itm;
	}

	FILE* fp;
	fp = fopen("RBTree.dot", "w+");
	fprintf(fp, "digraph G{n");
	WriteTree2File(fp, t.returenROOT(), t.returenROOT()->_parent);
	fprintf(fp, "}");
	fclose(fp);

	system("dot -Tpng -O RBTree.dot");
	system("RBTree.dot.png");

	return 0;
}

结果展示：