C++ 红黑树

目录

一、红黑树的概念和性质

二、实现红黑树

1、节点定义+构造

2、插入

3、左单旋&右单旋

4、中序遍历

5、检查平衡

6、获取树的高度

7、查找

8、析构

测试

完整版

---

一、红黑树的概念和性质

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

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

		Node* ppnode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

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

1. 首先，我们定义了三个指针变量：subR?指向父节点的右子节点，subRL?指向?subR?的左子节点，ppnode?指向父节点的父节点。

2. 我们将父节点的右子节点指向?subRL，这样父节点和?subR?就断开了连接。如果?subRL?不为空，我们还需要将其父节点指针指向父节点。

3. 接下来，我们将父节点的父节点指针指向?subR，将?subR?的左子节点指向父节点。

4. 如果父节点的父节点指针?ppnode?为空，表示父节点是根节点，我们将根节点指针?_root?指向?subR，并将根节点的父节点指针置为空。

5. 如果父节点的父节点指针?ppnode?不为空，我们需要根据父节点在其父节点的位置来更新指、针。如果父节点是其父节点的左子节点，我们将?subR?设置为其父节点的左子节点；否则，将?subR?设置为其父节点的右子节点。同时，我们还需要更新?subR?的父节点指针为?ppnode。

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

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

		Node* ppnode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

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

1. 首先，我们定义了三个指针变量：subL?指向父节点的左子节点，subLR?指向?subL?的右子节点，ppnode?指向父节点的父节点。

2. 我们将父节点的左子节点指向?subLR，这样父节点和?subL?就断开了连接。如果?subLR?不为空，我们还需要将其父节点指针指向父节点。

3. 接下来，我们将父节点的父节点指针指向?subL，将?subL?的右子节点指向父节点，以完成右旋转操作。

4. 如果父节点是根节点?_root，我们将根节点指针?_root?指向?subL，并将根节点的父节点指针置为空。

5. 如果父节点的父节点指针?ppnode?不为空，我们需要根据父节点在其父节点的位置来更新指针。如果父节点是其父节点的左子节点，我们将?subL?设置为其父节点的左子节点；否则，将?subL?设置为其父节点的右子节点。同时，我们还需要更新?subL?的父节点指针为?ppnode。

4、中序遍历

public:
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

5、检查平衡

private:
	bool _Check(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr) {
			if (benchmark != blackNum) {
				cout<< "某条路径黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
			blackNum++;

		if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

_Check函数是一个递归函数，用于检查从给定节点到其所有叶子节点的所有路径是否都包含相同数量的黑色节点，并且没有连续的红色节点。

1. 如果当前节点为空，那么我们就检查到达这个叶子节点的路径上的黑色节点数量是否等于基准值。如果不等于，那么就返回false。否则，返回true。

2. 如果当前节点是黑色的，那么我们就将黑色节点的数量加一。

3. 如果当前节点是红色的，并且它的父节点也是红色的，那么就返回false，因为这违反了红黑树的性质。

4. 最后，我们递归地检查当前节点的左子节点和右子节点。

public:
	bool IsBalance()
	{
		if (_root && _root->_col == RED) {
			cout << "根节点的颜色是红色" << endl;
			return false;
		}
		int benchmark = 0;
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK)
				benchmark++;
			cur = cur->_left;
		}
		return _Check(_root, 0, benchmark);
	}

• IsBalance函数首先检查根节点是否是黑色的。如果根节点是红色的，那么就返回false。
• 然后，我们计算从根节点到左子树的最左叶子节点的路径上的黑色节点数量，作为基准值。
• 最后，我们调用_Check函数，检查整棵树是否满足红黑树的性质。如果满足，那么就返回true。否则，返回false。

6、获取树的高度

public:
	int Height()
    {
		return _Height(_root);
	}
private:
	int _Height(Node* root)
    {
		if (root == nullptr)
			return 0;
		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);
		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

• Height?函数：这是一个获取树的高度的函数，用于计算树的高度。它调用了私有函数?_Height?来进行递归计算。

• _Height?函数：这是一个私有的获取节点高度的函数，用于递归地计算节点的高度。如果当前节点为空，返回 0；否则，计算左子树和右子树的高度，返回较大的高度加 1。

7、查找

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur){
		if (cur->_kv.first < key){
			cur = cur->_right;
		}
		else if (cur->_kv.first > key){
			cur = cur->_left;
		}
		else{
			return cur;
		}
	}

	return nullptr;
}

8、析构

public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}
private:
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

测试

void Test_RBTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,  };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
		cout << e << "插入：" << t1.IsBalance() << endl;
	}

	t1.InOrder();
	cout << t1.IsBalance() << endl;
}

void Test_RBTree2()
{
	srand(time(0));
	const size_t N = 5000000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
		//cout << t.IsBalance() << endl;
	}

	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
}

完整版

#pragma once

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

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

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < key) {
				cur = cur->_right;
			}
			else if (cur->_kv.first > key) {
				cur = cur->_left;
			}
			else {
				return cur;
			}
		}
		return 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);
		if (parent->_kv.first > kv.first){
			parent->_left = cur;
		}
		else{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED){
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent){
				Node* uncle = grandfather->_right;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED){
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//     g
					//   p   u
					// c 
					if (cur == parent->_left){
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else{
						//     g
						//   p   u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						//parent->_col = RED;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // (grandfather->_right == parent)
			{
				//    g
				//  u   p
				//        c
				Node* uncle = grandfather->_left;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED){
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//    g
					//  u   p
					//        c
					if (cur == parent->_right){
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else{
						//    g
						//  u   p
						//    c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	//根据规则检查
	bool IsBalance()
	{
		if (_root && _root->_col == RED) {
			cout << "根节点的颜色是红色" << endl;
			return false;
		}
		int benchmark = 0;
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK)
				benchmark++;
			cur = cur->_left;
		}
		return _Check(_root, 0, benchmark);
	}

	int Height()
	{
		return _Height(_root);
	}

private:
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

	bool _Check(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr) {
			if (benchmark != blackNum) {
				cout<< "某条路径黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
			blackNum++;

		if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

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

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

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

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

		Node* ppnode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

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

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

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

		Node* ppnode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

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