[数据结构与算法]C++下“红黑树”的简单模拟实现以及实现中遇见的问题

1.概念：

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

2.性质：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（说明：树中没有连续的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点（说明：每条路径黑色节点的数量相等）
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

最短路径：全黑
最长路径：一黑一红

假设每条路径黑节点的数量是：N
N <= 任意路径长度 <= 2N

3.个人理解：

问题一：不要自己随便举例子

这是三个节点依次插入二叉树的时候，他们颜色的变化
是否可以理解为：因为二叉树的“约定”使得他们的颜色一定会趋向某种特定状态，也就是说有一些节点的状态（假设三个节点，那么这三个节点一定是全黑？）（个人思考出的答案：对，也不对）

不对

那么这种情况也就是反例

对
补充一下，只能说有一些情况是完全不可能的，
即使这种情况是对的，但是这种情况不一定会出现

这种情况是符合二叉树的性质的，但是这种树是不存在的
原因解释：我们知道我们插入的节点的初始颜色都是红色的，那么为什么 cur1和cur2 是黑色?
假设此时cur1和2不存在，此时需要插入cur1，那么此时插入的就是一个红色的节点，因为cur1的父亲是红色的，根据约定，我们会改变上面的颜色，也就是说不会出现这种情况
即：这种情况是我们脑子随便臆想出来的反例，不符合人家的规则

问题二：是否有可能一个子树比另一个子树的高度高2倍

解决一：
极限情况下：
最短路径：全黑
最长路径：一黑一红
假设每条路径黑节点的数量是：N
N <= 任意路径长度 <= 2N

解决二：
还是按照问题一的思路来看
我们知道最长路径是一黑一红，
个人推导：长的那个路径下，最下面的叶子节点是红色的，
当你再向下插入的时候，红红就会传递上去改变其他节点颜色，甚至 左旋或者右旋

问题三：记住一个插入规则

插入的节点是红色的，而且在本次插入的时候，这个红色是不会变化的
他的高度（距离根节点）也是变化很小的（减1或者不变）

4.插入时的各种情况

补充说明：
cur：“新增”
p：“新增”的父亲
g：“新增”的祖父
u：叔叔节点

情况一：

情况二：

旋转的意义：
保证他是搜索树的规则情况下，降低高度

情况三：

insert代码

#pragma once
#include <time.h>

enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _kv(kv)
	{}
};

template<class K, class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		cur->_col = RED; // 新增节点
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 控制平衡
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//1.叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//情况一：
					//变色加继续向上调整
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					if (cur == parent->_left)
					{
						//情况二：
						//        g
						//     p
						//  c
						// 单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//parent=grandfather->_right;
					{
						//情况三：
						//        g
						//     p
						//        c
						// 双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else
			{ // parent == grandfather->_right

				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色+继续向上处理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					if (cur == parent->_right)
					{
						//情况二：
						//  g    
						//     p
						//        c
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//情况三：
						//  g
						//     p
						//  c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* parentParent = 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;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
	}
	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root;
};

void TestRBTree()
{
	RBTree<int, int> t;
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();

}

5.检查

引入：

红黑树性质：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（说明：树中没有连续的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点（说明：每条路径黑色节点的数量相等）
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

根据性质三，我们可以推出，红黑树中不可能有连个连续的红色节点

对于性质四，我们可以记录一条路径下的黑色节点数目，每当遍历一条路径，就可以判断，每条路径下的黑色节点数目是否是相同的

代码：

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点不是黑色的" << endl;
			return false;
		}

		//最左路径黑色节点数量作为基准值
		int banchmark = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
				++banchmark;
			left = left->_left;
		}

		int blackNum = 0;
		return _IsBalance(_root,banchmark,blackNum);
	}
	bool _IsBalance(Node* root,int banchmark,int blackNum)
	{
		if (root == nullptr)
		{
			if (banchmark != blackNum)
			{
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "出现连续红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}
		return _IsBalance(root->_left, banchmark, blackNum)
			&& _IsBalance(root->_right, banchmark, blackNum);
	}

6.迭代器

++

begin是最左子树的叶子节点
end不是最左子树的叶子节点，而是nullptr

减减

Find

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

7.深拷贝

引入问题：

在set中调用这个的时候

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

我们在内存监视中可以看到copy的地址和s的地址一样（浅拷贝）

困难点：

拷贝构造一个节点，不仅要拷贝他的val
还有他的 left ，right，parent并且这些值是不一样的，
这些值需要指向他们的l,f,p,

解决代码：

	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr) return nullptr;

		Node* newRoot = new Node(root->_data);
		newRoot->_col = root->_col;

		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		if (newRoot->_left)
			newRoot->_left->_parent = newRoot;
		if (newRoot->_right)
			newRoot->_right->_parent = newRoot;
		return newRoot;
	}

建议将上面的这段代码放入私有防止被破坏

operator=

	RBTree<K, T, KeyOfT>& operator=(RBTree<k, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

8.将map和set进行简单封装(最终代码)

RBTree.h

#pragma once
#include <time.h>

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)
		, _col(RED)
		, _data(data)
	{}
};

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

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

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

	Self& operator++(){
		//指向中序的下一个
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min=min->_left;
			}
			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && 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)
			{
				max = max->_right;
			}
			_node = max;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = 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;
	}
};

//set RBTree<K,K,SetKeyOfT>
//map RBTree<K,pair<K,V>,MapKeyOfT>
template<class K,class T, class KeyOfT>
struct RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		// 最左节点
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	iterator end()
	{
		return iterator(nullptr); 
	}

	RBTree()
		:_root(nullptr)
	{}
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}
	RBTree<K, T, KeyOfT>& operator=(RBTree<k, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}
	~RBTree()
	{
		Destory(_root);
		_root = nullptr;
	}

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

	pair<iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), 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 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* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 1、uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色+继续向上处理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					//        g
					//     p
					//  c

					//        g
					//     p
					//        c

					if (cur == parent->_left)
					{
						// 单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// 双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色+继续向上处理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					//  g    
					//     p
					//        c

					//  g
					//     p
					//  c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		return  make_pair(iterator(newNode), true);
	}
private:
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* parentParent = 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;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
	}

	void Destory(Node* root)
	{
		if (root == nullptr) return;

		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr) return nullptr;

		Node* newRoot = new Node(root->_data);
		newRoot->_col = root->_col;

		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		if (newRoot->_left)
			newRoot->_left->_parent = newRoot;
		if (newRoot->_right)
			newRoot->_right->_parent = newRoot;
		return newRoot;
	}

private:
	Node* _root;
};

Myset.h

#pragma once
#include "RBTree.h"

namespace sakeww
{
	template < class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

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

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

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

	void test_set()
	{
		set<int> s;
		s.insert(1);
		s.insert(4);
		s.insert(2);
		s.insert(24);
		s.insert(2);
		s.insert(12);
		s.insert(6);

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

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

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

MyMap.h

#pragma once
#include "RBTree1.h"

namespace sakeww
{
	template < class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;

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

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

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

		V& operator[](const K& key)
		{
			auto ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};

	void test_map()
	{
		map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字符串"));
		dict.insert(make_pair("map", "地图"));
		dict["right"];
		dict["right"] = "右边";
		dict["map"] = "地图，映射";

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

9. 适配器

map/set 封装红黑树 不是适配器
stack/queue/priority_queue 封装deque/vector 适配器
支持改变底层容器的才是适配器