红黑树+红黑树模拟实现map/set

红黑树

1.红黑树相关概念

1、红黑树是一种二叉树，只是每个节点都增加了一个存储位表示结点的颜色，颜色可以是red或者black。通过一系列规则限制，使得红黑树没有一条路径比其他路径长出两倍，这也可以说是接近平衡的。

(1).红黑树的性质

1.每个结点在我们看来不是红色就是黑色(概念上)
2.根节点必须是黑色的
3.如果一个节点是红色的，那么它的两个孩子节点必须是黑色的
4.对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5.每个叶子结点都是黑色的（此处的叶子结点指的是空结点）
为什么满足上面的性质，红黑树就能保证：最长路径中节点个数不会超过最短路径节点个数的两倍？
最长节点：一黑一红交替
最短节点：全黑
红黑树需要保证每个结点到其后代所有叶结点的简单路径上，包含相同数目的黑色结点

2. 红黑树核心代码实现

(1).红黑树结点的定义

enum Color
{
	RED,
	BLACK,
    
};//结点的颜色
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _kv;//结点的值域
	Color _col;//结点的颜色
	RBTreeNode(const T&kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

红黑树结点的构造函数为什么默认构造颜色为红色？
因为红黑树需要保证每个结点到其后代所有叶子结点上的所含黑色结点的个数是一样的，如果默认结点颜色是黑色，会破坏多条路径，插入红色却没关系，但是插入红色结点有可能违反另一条规则：红色结点的孩子必须是黑色。
并且无论什么时候根节点必须是黑色的
如果根节点是红色，将会违反规则，每条路径上黑色结点个数相等这个规则。

(2)插入的几种情况

1. 前提，插入是先按照二叉树的规则插入新节点，然后再检查是否违反规则，如果违反了，则对红黑树进行旋转着色处理
   2、因为新节点的默认颜色是红色，当插入结点的双亲结点颜色是黑色时，没有违反规则，不需要调整，当插入节点的双亲结点时红色的，或者因为插入结点之后的调整出现了连续两个红色的结点，就违反了红黑树的性质，此时需要分情况讨论。
   注意：下面所看到的树，可能时一颗完整的树，也可能是一颗子树, cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
   注意下面的三角形代表各种有可能出现的情况，下面的图都是抽象图，保证三角形都是符合红黑树的

Ⅰ插入的条件判断

while (parent && parent->_col == RED)
1

插入时先是按照二叉树的规则进行插入的，并且插入的默认节点颜色是红色，所以我们一开始的条件判断就是如果parent存在并且parent->col ==RED,说明违反了规则，此时我们要对子树进行调整。
如果满足上述条件，g节点一定存在吗？
一定存在，因为根节点一定是黑色，如果此时父节点不存在就违反红黑树的规则，所以满足条件后的g节点是一定存在的，至于是不是根节点，还得继续判断。

a.cur为红，p为红，u存在且为红

如果出现下图的情况，就得继续进入循环判断是哪种情况

b.cur为红，p为红，u不存在/存在且为黑

代码实现在点进这个链接后的评论区

3. 红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(logN)，红黑树不追求绝对的平衡，其只需保证最长路径不超过最短路径的两倍，相比较而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优

红黑树模拟实现map/set

由于set是两个模板参数是一样的；
map是>乍一看，如果将红黑树中的对应的那个Key去掉也行，set还可以有key，map也可以取出来key。
不行,因为类中可能有函数需要用到Key的接口
eg: iterator find(const Key&key) 此时如果没有第一个参数Key的话，set勉强可以，但是pair不行，因为pair调用rb_tree时，此时rb_tree的模板参数Value被推断出是pair,无法推出pair.first，也就无法得到此时Key的类型，像operator[]都是需要传递key的函数，所以不可以省略.

1.红黑树迭代器的实现

由于红黑树每个节点储存的都有很多不同种类的元素，迭代器是像指针一样的东西，所以此时红黑树的迭代器就有点类似于曾经的list迭代器，此时迭代器为什么会有三个模板参数我已经在
点击这篇博客即可说明

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
2
3
4
5
6
7
8
9

此时需要考虑以下几个问题：

(1).迭代器的++与–

红黑树迭代器的遍历结果是一个有序的序列。迭代器的遍历本质上是左中右，中序遍历
operator++
1.如果此时node->right !=nullptr
此时找到右子树的最左节点即可
2.此时_nude->right == nullptr
此时找到祖先里面，孩子是父亲左的那一个节点
operator–
1.如果此时_node->left !=nullptr
此时找到左子树的最右节点即可
2.如果此时 _node->left ==nullptr
此时找到祖先里，孩子是父亲右节点的那个

Self operator++()//表示的是中序的下一个
		{
			if (_node->_right == nullptr)
			{
				//此时找祖先里面,孩子是父亲左的那个
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			else
			{
				//此时找右子树的最左节点
				Node* subLeft = _node->_right;
				while (subLeft->_left)
				{
					subLeft = subLeft->_left;
				}
				_node = subLeft;
			}
			return *this;
		}

Self operator--()
		{
			if (_node->_left == nullptr)
			{
				//此时找祖先里面孩子是父亲右的那个
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			else
			{
				//左子树的最右节点
				Node* subRight = _node->_left;
				while (subRight->_right)
				{
					subRight = subRight->_right;
				}
				_node = subRight;
			}
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

(2)洪恩红黑树中的begin（）和end（）

STL明确规定，begin()和end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后可以得到一个有序的序列，所以begin可以放在红黑树中最小节点（即最左侧节点）的位置，end()位置是最大节点（最右侧节点)的下一个位置 为了方便，此时我们将end（）位置设置为nullptr,实际上是不能设置成nullptr，因为对end()位置的迭代器进行——操作,必须要能找到最后一个一个元素。
代码太简单，不粘贴了hhh

2.改造红黑树

通过上述源代码，可以了解到，红黑树的后面参数不谈（类似于空间配置器啥的），但是其前面的参数我们是可以模仿的。
template
K:代表的就是Key
T：在set代表的是K，但在map中代表的是pair
KeyofT:是一个仿函数，该仿函数是set和map彼此中的一个内部类，作用是提取其中的K，提取set中的K，和pair中的Key。
为什么要这样做？
因为set和map本质上是靠红黑树的封装，他们底层的代码都是红黑树，红黑树的代码实现一份就可以了，然后让map和set调用即可，此时只需要将传入的参数改变一下即可.
下面贴一个set的模拟实现，所有代码请点击下面链接
链接在最下面
set封装红黑树

template<class K>
	class set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}

		};
	public:
		typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyofT>::const_iterator const_iterator;
		iterator begin()const
		{
			
			//关于这个函数必须加const的问题
			/*
			* 如果不加const,那么此时的this指针
			* 调用函数返回的是普通迭代器，不是
			* const迭代器,而set无论是普通迭代器
			* 还是const迭代器都是const迭代器
			* 如果不加const迭代器的话，此时是
			* 普通迭代器转换成const迭代器
			* 这是错误的
			*/
			return _t.Begin();
		}
		
		iterator end()const
		{
			return _t.End();
		}
		pair<iterator, bool>insert(const K& key)
		{
			//用普通迭代器去构造const迭代器
			auto ret = _t.Insert(key);
			return pair<iterator, bool>(iterator(ret.first._node), ret.second);
		}
		iterator find(const K& key)
		{
			return _t.Find(key);
		}
		

	private:
		RBTree<K, K, SetKeyofT> _t;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

模拟实现set中有两个需要注意

a.begin()和end()

因为set的迭代器本质上都是const_iterator，即使iterator也是由const迭代器typedef而成的，所以如果此时begin()函数后不加const
直接是iterator begin() { return _t.Begin()； }
那么此时set中的this就不是const this，此时该函数调用就是this->Begin()，返回的就是普通的迭代器，但是set中迭代器都是const_iterator，此时就是用普通迭代器去构造const迭代器，这本质就是错误的。所以我们要在begin和end后加const

b.pairinsert(const K& key)

pair<iterator, bool>insert(const K& key)
		{
			//用普通迭代器去构造const迭代器
			auto ret = _t.Insert(key);
			return pair<iterator, bool>(iterator(ret.first._node), ret.second);
		}
1
2
3
4
5
6

此时不能直接return _t.Insert(key)
因为红黑树中返回的迭代器都是普通迭代器，但是set中的都是const迭代器，所以说，我们先调用红黑树中的Insert，然后用普通迭代器构造const迭代器。map则没有这样的顾虑，map既有普通迭代器又有const迭代器.

代码完整实现