[C++] RBTree红黑树的模拟实现

定义

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

性质

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

模拟实现

1）实现基本框架

定义结点

• 采用三叉链表的形式定义树的结点，用pair存放数据，增加表示结点颜色的成员变量，结点默认为红色；

enum Colors{
	red,
	black
};

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

	BRTreeNode(const pair<K, V>& kv, Colors color = red)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_color(color){
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

其构造、拷贝构造、赋值重载、析构函数同AVLTree

2）实现基本操作

insert插入操作

• 先找待插入位置，然后插入新结点，控制其性质
• 控制红黑树性质：

1. 若其父结点是黑色，不需要处理，插入完成；
2. 若其父结点为红色，需要处理，关键是看叔叔结点：
3. 情况1：叔叔结点存在且为红色—p、u置黑，g置红；然后继续向上处理
4. 情况2：叔叔结点不存在或者为黑色—若cur、p、g在一条直线上，只需要单旋处理；若cur、p、g不在一条直线上，需要进行双旋处理。

	pair<node*, bool> insert(const pair<K, V>& kv){
		if (_root == nullptr){
			_root = new node(kv);
			_root->_color = black;  //根结点是黑色的
			return make_pair(_root, true);
		}

		//找待插入结点的位置
		node* parent = nullptr;
		node* cur = _root;
		while (cur != nullptr){
			if (kv.first < cur->_kv.first){
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first){
				parent = cur;
				cur = cur->_right;
			}
			else{
				return make_pair(cur, true);
			}
		}
		//找到了待插入结点的位置:插入新结点
		node* newnode = new node(kv);
		cur = newnode;
		if (cur->_kv.first < parent->_kv.first){
			parent->_left = cur;
			cur->_parent = parent;
		}
		else{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//控制该树的性质，使其满足红黑树的要求
		//1. 若parent为黑色，不需要处理，插入完成
		if (parent->_color == black)
			return make_pair(cur, true);
		
		//2. parnet为红色，需要分情况进行处理
		while (parent && parent->_color == red){  //parnet为红,一定有grandparent结点
			node* grandparent = parent->_parent;

			if (parent == grandparent->_left){  //parent在左边
				node* uncle = grandparent->_right;
				//情况1：uncle为red
				if (uncle && uncle->_color == red){  
					parent->_color = black;
					uncle->_color = black;
					grandparent->_color = red;
					//继续向上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else{  //情况2：uncle不存在或uncle为black
					if (cur == parent->_left){  //右单旋
						RotateR(grandparent);
						parent->_color = black;
						grandparent->_color = red;
					}
					else{  //先左单旋再右单旋
						RotateL(parent);
						RotateR(grandparent);
						cur->_color = black;
						grandparent->_color = red;
					}
					break;  //情况2不需要再继续向上处理，因为旋转后新的"根结点"都是黑色的
				}
			}
			else{  //parent在右边
				node* uncle = grandparent->_left;
				if (uncle && uncle->_color == red){
					parent->_color = black;
					uncle->_color = black;
					grandparent->_color = red;
					//继续向上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else{
					if (cur == parent->_right){
						RotateL(grandparent);
						parent->_color = black;
						grandparent->_color = red;
					}
					else{
						RotateR(parent);
						RotateL(grandparent);
						cur->_color = black;
						grandparent->_color = red;
					}
					break;
				}
			}
		}
		//处理根结点为黑色
		_root->_color = black;
		return make_pair(newnode, true);
	}

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

find查找、operator[ ]操作同AVLTree

判定是否是RBTree

验证其是否为二叉搜索树

验证其是否为满足红黑树的性质

	bool isBalance(){
		if (_root == nullptr)
			return true;
		//验证规则2
		if (_root->_color != black){
			cout << "根结点不是黑色" << endl;
			return false;
		}
		//以最左端的路径为参照，计算其黑色结点的数目
		node* cur = _root;
		int blacknum = 0;
		while (cur != nullptr){
			if (cur->_color == black)
				blacknum++;
			cur = cur->_left;
		}
		//使用子函数验证规则3、4
		int count = 0;
		return _isBalance(_root, blacknum, count);
	}

	bool _isBalance(node* root, int blackNum, int count){
		if (root == nullptr){
			if (count != blackNum){
				cout << "各路径黑色结点的数目不相等" << endl;
				return false;
			}
			return true;
		}
		
		if (root->_color == black)
			count++;
		
		//验证规则2：拿自己与父结点的颜色比较，看是否都为红色的
		node* parent = root->_parent;
		if (root->_color == red && parent->_color == red)
			return false;

		return _isBalance(root->_left, blackNum, count) &&
			_isBalance(root->_right, blackNum, count);
	}
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

3）实现其迭代器

template <class T, class Ref, class Ptr>
struct BRIterator{
	typedef Ref reference;
	typedef Ptr pointer;
	typedef BRTreeNode<T> node;
	typedef BRIterator<T, Ref, Ptr> self;

	node* _pnode;

	BRIterator(node* node)
		:_pnode(node){
	}

	self& operator++(){
		//如果_pnode的右不为空，++就是其右子树的最左端结点
		if (_pnode->_right != nullptr){
			node* cur = _pnode->_right;
			while (cur->_left != nullptr){
				cur = cur->_left;
			}
			_pnode = cur;
		}
		else{//如果_pnode的右为空：若其不是父亲的右孩子，++就是其父结点；否则继续沿着三叉链表向上找
			node* cur = _pnode;
			node* parent = cur->_parent;
			while (parent && parent->_right == cur){
				cur = parent;
				parent = parent->_parent;
			}
			_pnode = parent;
		}
		return *this;
	}

	self& operator--(){
		//如果_pnode的左不为空，--就是其左子树的最右端结点
		if (_pnode->_left != nullptr){
			node* cur = _pnode->_left;
			while (cur->_right != nullptr){
				cur = cur->_right;
			}
			_pnode = cur;
		}
		else{//如果_pnode的左为空：若其不是父亲的左孩子，--就是其父结点；否则继续沿着三叉链表向上找
			node* cur = _pnode;
			node* parent = cur->_parent;
			while (parent && cur == parent->_left){
				cur = parent;
				parent = parent->_parent;
			}
			_pnode = parent;
		}
		return *this;
	}

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

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

	bool operator!=(const self& s){
		return _pnode != s._pnode;
	}

	bool operator==(const self& s){
		return _pnode == s._pnode;
	}

};
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72