红黑树/红黑树迭代器封装（C++）

标签：Node cur parent 红黑树 C++ grandfather col 迭代节点

本篇将会较为全面的讲解有关红黑树的特点，插入操作，然后使用代码模拟实现红黑树，同时还会封装出红黑树的迭代器。

在 STL 库中的 set 和 map 都是使用红黑树封装的，在前文中我们讲解了 AVL树，对于红黑树和 AVL 树来说，这两种树都是效率很高的搜索二叉树，但是相对而言 AVL 树会更加接近平衡二叉树，但是用于封装 set 和 map 的却是红黑树，这是因为虽然红黑树不是很接近平衡二叉树，但是和 AVL 树的搜索效率相比较其实相差不是很多，相反而言，对于红黑树在插入时的效率会比 AVL 树更高，所以封装 set 和 map 选择使用了红黑树。

如下：

目录

1. 红黑树

All code

红黑树的特性

红黑树节点的定义

红黑树的插入操作

红黑树检测与暴力测试

2. 红黑树迭代器封装

迭代器的测试

1. 红黑树

All code

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

enum Colour { 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;
	Colour _col;

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

// k v
template <class K, class V>
class Iterator {
	typedef Iterator Self;
	typedef BRTreeNode<K, V> Node;
	typedef pair<K, V>& Ref;
	typedef pair<K, V>* Ptr;
public:
	Iterator(Node* node)
		:_node(node)
	{}

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

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

	Self operator++() {
		// left middle right
		// 如果有右孩子节点，找出右孩子节点中的最左节点
		// 如果没有右孩子节点，需要不断向上迭代，找到最左节点
		if (_node->_right != nullptr) {
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left) {
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_left) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self operator--() {
		// 若当前迭代器为null，返回最右节点
		// left middle right
		// 如果有左孩子，找出左孩子中的最大节点
		// 如果没有左孩子，需要向上迭代


		if (_node->_left != nullptr) {
			Node* rightMin = _node->_left;
			while (rightMin && rightMin->_right) {
				rightMin = rightMin->_right;
			}
			_node = rightMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_right) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& it) {
		return _node != it._node;
	}

private:
	Node* _node;
};

template <class K, class V>
class BRTree {
	typedef BRTreeNode<K, V> Node;
public:
	typedef Iterator<K, V> iterator;
	// 封装迭代器
	iterator begin() {
		// 找到最左节点
		Node* leftMin = _root;
		while (leftMin && leftMin->_left) {
			leftMin = leftMin->_left;
		}
		return iterator(leftMin);
	}

	iterator end() {
		return iterator(nullptr);
	}
	// 插入
	bool insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur) {
			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 false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < cur->_kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		cur->_parent = parent;
		// 开始调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			// 先判断当前插入的节点是在爷爷节点的左边还是右边
			if (parent == grandfather->_left) {
				Node* uncle = grandfather->_right;
				// 一共存在两种情况，叔叔节点存在且叔叔节点不为黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					// 更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else {
					// 现在这种情况属于叔叔节点不存在或者存在为黑
					// 需要判断当前属于什么情况
					if (cur == parent->_left) {
						//      g           p
						//   p     u -->  c   g
						// c                    u
						// 右旋即可
						RotateRight(grandfather);
						parent->_col = BLACK;
						cur->_col = grandfather->_col = RED;
					}
					else {
						//      g            g          c
						//   p     u -->   c   u -->  p   g
						//     c         p                   u
						// 先左旋，后右旋
						RotateLeft(parent);
						RotateRight(grandfather);
						cur->_col = BLACK;
						parent->_col = grandfather->_col = RED;
					}
					break;
				}
			}
			else {
				Node* uncle = grandfather->_left;
				// 一共存在两种情况，叔叔节点存在且叔叔节点为黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					// 更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else {
					if (cur == parent->_right) {
						//     g             p 
						//   u   p   -->   g   c
						//         c     u
						// 对g进行左旋
						RotateLeft(grandfather);
						grandfather->_col = cur->_col = RED;
						parent->_col = BLACK;
					}
					else {
						//     g             g            c
						//   u   p   -->   u   c   -->  g   p
						//      c                p    u
						// 先右旋，后左旋
						RotateRight(parent);
						RotateLeft(grandfather);
						cur->_col = BLACK;
						grandfather->_col = parent->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	// 右旋
	void RotateRight(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandfather = parent->_parent;

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

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

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

	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandfather = parent->_parent;

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

		parent->_parent = subR;
		subR->_left = parent;

		if (grandfather == nullptr) {
			_root = subR;
			_root->_parent = nullptr;
		}
		else if (grandfather->_left == parent) {
			grandfather->_left = subR;
			subR->_parent = grandfather;
		}
		else if (grandfather->_right == parent) {
			grandfather->_right = subR;
			subR->_parent = grandfather;
		}
		else {
			assert(false);
		}
	}

	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}

	bool isBalance() {
		// 需要检查黑色节点个数，需要检查红色节点的分布
		int refNum = 0;
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK)
				refNum++;
			cur = cur->_left;
		}
		return _Cheak(_root, 0, refNum);
	}
private:
	bool _Cheak(Node* root, int blackNum, int refNum) {
		if (root == nullptr) {
			if (refNum != blackNum) {
				cout << ":存在黑节点不平衡" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED) {
			cout << root->_kv.first << ":存在连续红节点" << endl;
			return false;
		}
		if (root->_col == BLACK) blackNum++;
		return _Cheak(root->_left, blackNum, refNum) && _Cheak(root->_right, blackNum, refNum);
	}

	void _InOrder(Node* root) {
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

红黑树的特性

首先先给出红黑树的概念：

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

关于红黑树的特性，一共可以总结为以下四点：

1. 每个节点不是黑色就是红色；

2. 根节点是黑色的；

3. 如果一个节点是红色的，则他的两个孩子节点的颜色是黑色的。

4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

5. 对于叶子节点都是黑色的（这里所指的黑色节点是指的是空结点）。

红黑树的特性如上，那么关于红黑树是如何做到从根节点到叶子节点的路径中，最长的不会超过最短的两倍的呢？

其实关于这个答案很简单，这是由上的1、3、4条性质所决定的，每条路径的黑色节点个数相同，并且一个节点不是黑色节点就是红色节点，所以对于最短路径可能为全都是黑色节点的路径，对于最长路径也不过是红色节点和黑色节点相混合的（因为红色节点的子节点必须为黑色节点），刚好是最短路径的两倍。

红黑树节点的定义

首先先给出红黑树的节点定义，该节点的定义和平衡二叉树十分相似，节点的指针包含父节点的指针、左右孩子的节点的指针，然后还有表示保存演示的变量，然后就是保存键值的变量，如下：
// 颜色
enum Colour { 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;
	Colour _col;

	BRTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
如上的构造函数，我们将最新生成的节点默认为红色节点，那么为什么需要将节点默认设置为红色节点呢？

这是因为倘若我们将节点的颜色设置为黑色节点，那么每一次在叶子节点处插入的节点也是黑色节点，但是这个使用就会出现一个问题，也就是刚插入节点的分支相对于其他分支多了一个黑色节点，和其他的性质对不上了。但是当我们插入的节点为红色节点的时候，就算是在红色节点下添加红色节点，我们也可以通过不断向上进行调整，调整到符合红黑树的性质。

红黑树的插入操作

关于红黑树的操作而言，其大致逻辑和二叉搜索树一致，不过我们需要在插入之后对插入的节点进行调整，调整到满足红黑树的特性。上面我们已经说过，我们每一次插入是节点为红色节点，所以现在我们需要分别讨论出现连续红色节点的调整方法：

首先先给出一些特殊的节点：插入的节点为根节点的时候，直接将根节点的颜色设置为黑色。另外，若插入在黑色节点的后面就不需要调整。

由于二叉树是对称的，所以对应的操作也是对称的，出现一种情况就会有与之对应的第二种情况出现（比如插入的位置为爷爷节点的左子树或者右子树），所以只需要分析一种即可：

关于红黑树的调整，其中一个比较关键的节点就算叔叔节点（父亲节点的兄弟节点），叔叔节点的特性将决定我们如何调整我们的红黑树。有关叔叔节点的特性，一共存在两种情况：（叔叔节点存在且不为红色），以及（叔叔节点不存在或者叔叔节点存在为黑色）。首

先先谈论叔叔节点存在且为红色节点的情况：

如上所示的调整方法，当我们插入的位置为红色节点的后面，并且叔叔节点存在且为红色，我们可以将爷爷节点调整为红色，然后将父亲节点和叔叔节点调整为黑色节点即可，这样调整的话，也不会影响各子树的黑色节点的数量，同时还可以将连续的红色节点拆分，但是需要注意的一点是，关于爷爷节点的上方的节点，若原爷爷节点上方的节点为红色节点，那么我们还需要进行迭代调整。

第二种情况，叔叔不存在或者叔叔节点存在且为黑色节点的情况，如下：

如上图所示，叔叔节点存在且为黑和叔叔节点不存在，进行的操作其实是相同的：我们只需要对爷爷节点进行右旋，然后将父节点设置为黑色节点，然后将爷爷节点设置为红色即可，根本不需要管叔叔节点处于什么样的状况。并且这样调整之后，不需要继续向上调整，这是因为调整之后原爷爷节点的位置还是黑色，所以不用在继续向上调整。

以上只是当插入节点的位置为父节点的左边，还会有插入节点为父节点的右边的情况，如下：

对于这种情况我们只需要对父节点进行左旋，然后对爷爷节点右旋。就可以解决问题了。

关于如上的情况我们一直讨论情况是插入的节点在爷爷节点的左边，所以当插入在爷爷节点右边的时候，只需要相对以上情况对称选择调整或者向上调整即可。另外关于旋转的代码直接给出。

所以关于的插入的代码为：
// 插入
bool insert(const pair<K, V>& kv) {
	if (_root == nullptr) {
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur) {
		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 false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first < cur->_kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;
	// 开始调整
	while (parent && parent->_col == RED) {
		Node* grandfather = parent->_parent;
		// 先判断当前插入的节点是在爷爷节点的左边还是右边
		if (parent == grandfather->_left) {
			Node* uncle = grandfather->_right;
			// 一共存在两种情况，叔叔节点存在且叔叔节点不为黑色
			if (uncle && uncle->_col == RED) {
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				// 更新
				cur = grandfather;
				parent = cur->_parent;
			}
			else {
				// 现在这种情况属于叔叔节点不存在或者存在为黑
				// 需要判断当前属于什么情况
				if (cur == parent->_left) {
					//      g           p
					//   p     u -->  c   g
					// c                    u
					// 右旋即可
					RotateRight(grandfather);
					parent->_col = BLACK;
					cur->_col = grandfather->_col = RED;
				}
				else {
					//      g            g          c
					//   p     u -->   c   u -->  p   g
					//     c         p                   u
					// 先左旋，后右旋
					RotateLeft(parent);
					RotateRight(grandfather);
					cur->_col = BLACK;
					parent->_col = grandfather->_col = RED;
				}
				break;
			}
		}
		else {
			Node* uncle = grandfather->_left;
			// 一共存在两种情况，叔叔节点存在且叔叔节点为黑色
			if (uncle && uncle->_col == RED) {
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				// 更新
				cur = grandfather;
				parent = cur->_parent;
			}
			else {
				if (cur == parent->_right) {
					//     g             p 
					//   u   p   -->   g   c
					//         c     u
					// 对g进行左旋
					RotateLeft(grandfather);
					grandfather->_col = cur->_col = RED;
					parent->_col = BLACK;
				}
				else {
					//     g             g            c
					//   u   p   -->   u   c   -->  g   p
					//      c                p    u
					// 先右旋，后左旋
					RotateRight(parent);
					RotateLeft(grandfather);
					cur->_col = BLACK;
					grandfather->_col = parent->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

void RotateRight(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* grandfather = parent->_parent;

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

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

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

void RotateLeft(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* grandfather = parent->_parent;

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

	parent->_parent = subR;
	subR->_left = parent;

	if (grandfather == nullptr) {
		_root = subR;
		_root->_parent = nullptr;
	}
	else if (grandfather->_left == parent) {
		grandfather->_left = subR;
		subR->_parent = grandfather;
	}
	else if (grandfather->_right == parent) {
		grandfather->_right = subR;
		subR->_parent = grandfather;
	}
	else {
		assert(false);
	}
}

红黑树检测与暴力测试

将根据以上写出的代码给出对应的检测代码，其中主要检测红黑树是否平衡（满足红黑树特性），如下：

bool _Cheak(Node* root, int blackNum, int refNum) {
	if (root == nullptr) {
		if (refNum != blackNum) {
			cout << ":存在黑节点不平衡" << endl;
			return false;
		}
		return true;
	}
	if (root->_col == RED && root->_parent->_col == RED) {
		cout << root->_kv.first << ":存在连续红节点" << endl;
		return false;
	}
	if (root->_col == BLACK) blackNum++;
	return _Cheak(root->_left, blackNum, refNum) && _Cheak(root->_right, blackNum, refNum);
}

bool isBalance() {
	// 需要检查黑色节点个数，需要检查红色节点的分布
	int refNum = 0;
	Node* cur = _root;
	while (cur) {
		if (cur->_col == BLACK)
			refNum++;
		cur = cur->_left;
	}
	return _Cheak(_root, 0, refNum);
}

检测代码如下：

void BRTreeTest01() {
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// {16, 3, 7, 11, 9, 26, 18, 14, 15}
	BRTree<int, int> tree;

	for (auto e : a) {
		
		tree.insert(make_pair(e, e));
	}
	tree.InOrder();
	cout << tree.isBalance() << endl;
}

void BRTreeTest02() {
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (int i = 0; i < N; i++) {
		v.push_back(rand() + 1);
	}
	size_t begin1 = clock();
	BRTree<int, int> tree;
	for (auto e : v)
		tree.insert({ e, e });
	size_t end1 = clock();
	cout << "insert" << end1 - begin1 << endl;

	cout << tree.isBalance() << endl;

}

其中第一个测试为普通测试，第二个测试为压力测试。如下：

2. 红黑树迭代器封装

我们前文中已经提到关于红黑树可以用于封装 set 和 map，那么关于这两个容器也会存在迭代器，我们现在直接在红黑树阶段封装一个迭代器。

关于红黑树的迭代器，其中主要指向的是红黑树的节点，所以我们的迭代器主要为一个指向节点的指针，然后我们还需要对我们的迭代器进行运算符重载，比如常用的 * 解引用， ->，还有 != 操作符。还有++ 与 -- 运算符重载。如下：
template <class K, class V>
class Iterator {
	typedef Iterator Self;
	typedef BRTreeNode<K, V> Node;
	typedef pair<K, V>& Ref;
	typedef pair<K, V>* Ptr;
public:
	Iterator(Node* node)
		:_node(node)
	{}

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

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

	Self operator++() {
		// left middle right
		// 如果有右孩子节点，找出右孩子节点中的最左节点
		// 如果没有右孩子节点，需要不断向上迭代，找到最左节点
		if (_node->_right != nullptr) {
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left) {
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_left) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self operator--() {
		// left middle right
		// 如果有左孩子，找出左孩子中的最大节点
		// 如果没有左孩子，需要向上迭代


		if (_node->_left != nullptr) {
			Node* rightMin = _node->_left;
			while (rightMin && rightMin->_right) {
				rightMin = rightMin->_right;
			}
			_node = rightMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_right) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& it) {
		return _node != it._node;
	}

private:
	Node* _node;
};
如上的操作中，最为麻烦的操作就算 ++ 和 --，因为在红黑树中的节点并不是连续的，而是相互之间都是使用左右子树和父亲指针所维护的指针所连接起来的。

对于 ++ 操作，我们需要取得下一个节点，根据中序遍历原则（左中右），当右子树不为空的时候，返回右子树中的最小节点，若右子树为空的时候，这个时候只能向上迭代，直到为祖先节点的左子树的时候，就可以停止迭代了，这个祖先节点就是我们要找的节点。

-- 运算符重载和 ++ 相似，只不过一切操作都是相反的而已。

另外，我们还需要在红黑树中定义 begin 和 end 函数，关于 begin 函数就是返回树的最左节点，但是关于 end 函数，我们这里直接返回的是指向 nullptr 的迭代器，但是这样会存在一个问题，也就是若我们直接给一个指向 end 的迭代器，我们并不能找到以上的树中的节点。

迭代器的测试

关于迭代器的测试如下：

void BRTreeTest03() {
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };
	BRTree<int, int> tree;
	for (auto e : a) 
		tree.insert(make_pair(e, e));
	
	auto it = tree.begin();
	while (it != tree.end()) {
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}

标签：Node,cur,parent,红黑树,C++,grandfather,col,迭代,节点
From： https://blog.csdn.net/m0_74830524/article/details/139360168