C++语法（20）---- 模拟红黑树-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++语法（20）---- 模拟红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C++语法（19）---- 模拟AVL树_哈里沃克的博客-CSDN博客https://blog.csdn.net/m0_63488627/article/details/130229501?spm=1001.2014.3001.5501

1.红黑树介绍

2.模拟实现

1.枚举红黑颜色

2.节点的定义

3.树类框架

4.插入

5.检查

3.代码实现

1.红黑树介绍

最长路径不超过最短路径的两倍，近似平衡

最短：全黑

最长：一半黑一半红

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

2.根节点是黑色

3.如果一个节点是红色，它的两个孩子节点是黑色

4.每条路径都有相同数量的黑色节点

5.叶子节点(NIL节点)是黑的

满二叉树：全黑，或者每条路径一黑一红

较优情况：越均衡即越平衡

最差红黑树：左边全黑，右边一黑一红

较差情况：越不均衡

对比起AVL树，其实红黑树没有那么的较劲平衡，AVL的平衡得益于它不断的旋转。但是红黑树为了一些性能牺牲了平衡，减少了旋转的情况。

2.模拟实现

1.枚举红黑颜色

enum Color
{
	Black,
	Red,
};

2.节点的定义

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

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

定义一个节点时要注意其颜色：不过黑红的地位有所不同，选择决定后续的执行是否简单

选择红色：违背红色不能连续出现

选择黑色：违背整体路径黑色数量一致

我们认为选择红色更好，因为红色调节节点即可，黑色调节整个路径

3.树类框架

template<class K, class V>
class BRTree
{
private:
	Node* _root = nullptr;
};

4.插入

1.插入的头节点为根节点，根节点的颜色为黑色

2.普通插入的逻辑和搜索二叉树的逻辑一致

3.到这里就需判断是否两个红色节点连续，下面的问题就是调节双红色问题

调节双红色问题

情况一

插入红色节点其父节点和叔叔节点都是红色，那么我们要调整父节点和叔叔节点为黑色，不过如果只是调整这一步，那么这条树的分支就比别的树黑色节点多一个，所以我们还要更新祖父节点为红色，但是祖父为红不能保证它的父节点是黑的，所以我们仍然要往上判断

情况二

单旋加变色

叔叔节点是黑色或者不存在，如果只是把父节点变黑是不够的，因为高度超了，所以我们要用到左右旋。

情况三

双旋加变色

这样就变成了情况二

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->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return false;
	}

	//走到这cur就是要插入的位置
	//cur要连接parent，parent也要连接cur---判断靠kv的大小
	cur = new Node(kv);
	if (parent->_kv.first > cur->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == Red)
	{
		Node* grandparent = parent->_parent;
		//parent分在grandparent左右
		if (grandparent->_left == parent)
		{
			//关键是看uncle节点不存在/红色/黑色的情况
			Node* uncle = grandparent->_right;
			//1.uncle红
			//parent和uncle变黑，grandparent变红
			//grandparent变红需要往上判断
			if (uncle && uncle->_col == Red)
			{
				grandparent->_col = Red;
				parent->_col = uncle->_col = Black;

				cur = grandparent;
				parent = cur->_parent;
			}
            else  //uncle不存在/黑色
			{
				//2.cur也是parent的左边，uncle不存在/黑色
				//右旋grandparents，parent变黑，
				if (cur == parent->_left)
				{
					_RotateR(grandparent);
					parent->_col = Black;
					grandparent->_col = Red;
				}
				//3.cur是parent的右边，uncle不存在/黑色
				//左旋parent再右旋grandparents,cur变黑，grandparents变红
				else
				{
					_RotateL(parent);
					_RotateR(grandparent);
					cur->_col = Black;
					grandparent->_col = Red;
				}

				//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环
				break;
			}
				
		}
        else
		{
		Node* uncle = grandparent->_left;

		    //1.uncle红
		    //parent和uncle变黑，grandparent变红
		    //grandparent变红需要往上判断
		    if (uncle && uncle->_col == Red)
		    {
			    grandparent->_col = Red;
			    parent->_col = uncle->_col = Black;

			    cur = grandparent;
			    parent = cur->_parent;
		    }
			else  //uncle不存在/黑色
			{
				//2.cur也是parent的右边，uncle不存在/黑色
				//左旋grandparents，parent变黑，
				if (cur == parent->_right)
				{
					_RotateL(grandparent);
					parent->_col = Black;
					grandparent->_col = Red;
				}
				//3.cur是parent的右边，uncle不存在/黑色
				//右旋parent再左旋grandparents,cur变黑，grandparents变红
				else
				{
					_RotateR(parent);
					_RotateL(grandparent);
					cur->_col = Black;
					grandparent->_col = Red;
				}

				//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环
				break;
			}
		}
	}
	_root->_col = Black;
	return true;
}

5.检查

inspect函数

1.空树返回true

2.根节点是否是红的

3.先遍历最左边，得到这个分支的黑色节点数作为参考

check函数

1.传入参考黑色节点个数

2.计数每一分支的黑色节点数，递归到底部，可对照节点数是否满足

3.递归遍历看看有没有连续的红色节点文章来源地址https://www.toymoban.com/news/detail-427249.html

private: 
bool check(Node* root, size_t& reference, size_t num)
{
	if (root == nullptr)
	{
		if (num != reference)
		{
			cout << "路径长度有问题" << endl;
			return false;
		}

		return true;
	}
			

	if (root->_col == Red && root->_parent && root->_parent->_col == Red)
	{
		cout << "节点连续红色" << endl;
		return false;
	}
	
	if (root->_col == Black)
		num++;

	return check(root->_left, reference, num) && check(root->_right, reference, num);
}

bool _Inspect(Node* root)
{
	//空树也是红黑树
	if (_root == nullptr)
		return true;

	//检测根节点是否为黑色
	if (_root->_col != Black)
	{
		cout << "根节点是红色的" << endl;
		return false;
	}
			
	size_t leftNum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == Black)
				leftNum++;
			cur = cur->_left;
	}
	//检测所有路径黑色节点的数量是否一样
	//检测相邻节点是不是都是红色的
	return check(_root, leftNum, 0);
}

3.代码实现

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

enum Color
{
	Black,
	Red,
};

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

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

template<class K, class V>
class BRTree
{
public:
	typedef BRTreeNode<K, V> Node;
	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}

		//走到这cur就是要插入的位置
		//cur要连接parent，parent也要连接cur---判断靠kv的大小
		cur = new Node(kv);
		if (parent->_kv.first > cur->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == Red)
		{
			Node* grandparent = parent->_parent;
			//parent分在grandparent左右
			if (grandparent->_left == parent)
			{
				//关键是看uncle节点不存在/红色/黑色的情况
				Node* uncle = grandparent->_right;
				//1.uncle红
				//parent和uncle变黑，grandparent变红
				//grandparent变红需要往上判断
				if (uncle && uncle->_col == Red)
				{
					grandparent->_col = Red;
					parent->_col = uncle->_col = Black;

					cur = grandparent;
					parent = cur->_parent;
				}
				else  //uncle不存在/黑色
				{
					//2.cur也是parent的左边，uncle不存在/黑色
					//右旋grandparents，parent变黑，
					if (cur == parent->_left)
					{
						_RotateR(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;
					}
					//3.cur是parent的右边，uncle不存在/黑色
					//左旋parent再右旋grandparents,cur变黑，grandparents变红
					else
					{
						_RotateL(parent);
						_RotateR(grandparent);
						cur->_col = Black;
						grandparent->_col = Red;
					}

					//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环
					break;
				}
				
			}
			else
			{
				Node* uncle = grandparent->_left;

				//1.uncle红
				//parent和uncle变黑，grandparent变红
				//grandparent变红需要往上判断
				if (uncle && uncle->_col == Red)
				{
					grandparent->_col = Red;
					parent->_col = uncle->_col = Black;

					cur = grandparent;
					parent = cur->_parent;
				}
				else  //uncle不存在/黑色
				{
					//2.cur也是parent的右边，uncle不存在/黑色
					//左旋grandparents，parent变黑，
					if (cur == parent->_right)
					{
						_RotateL(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;
					}
					//3.cur是parent的右边，uncle不存在/黑色
					//右旋parent再左旋grandparents,cur变黑，grandparents变红
					else
					{
						_RotateR(parent);
						_RotateL(grandparent);
						cur->_col = Black;
						grandparent->_col = Red;
					}

					//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环
					break;
				}
			}
		}
		_root->_col = Black;
		return true;
	}

	void Print()
	{
		_Print(_root);
		cout << endl;
	}

	bool Inspect()
	{
		return _Inspect(_root);
	}

private: 
	bool check(Node* root, size_t& reference, size_t num)
	{
		if (root == nullptr)
		{
			if (num != reference)
			{
				cout << "路径长度有问题" << endl;
				return false;
			}

			return true;
		}
			

		if (root->_col == Red && root->_parent && root->_parent->_col == Red)
		{
			cout << "节点连续红色" << endl;
			return false;
		}
		
		if (root->_col == Black)
			num++;

		return check(root->_left, reference, num) && check(root->_right, reference, num);
	}

	bool _Inspect(Node* root)
	{
		//空树也是红黑树
		if (_root == nullptr)
			return true;

		//检测根节点是否为黑色
		if (_root->_col != Black)
		{
			cout << "根节点是红色的" << endl;
			return false;
		}
			
		size_t leftNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == Black)
				leftNum++;
			cur = cur->_left;
		}
		//检测所有路径黑色节点的数量是否一样
		//检测相邻节点是不是都是红色的
		return check(_root, leftNum, 0);
	}

	void _Print(Node*& cur)
	{
		if (cur == nullptr)
			return;
		_Print(cur->_left);
		cout << cur->_kv.first << " ";
		_Print(cur->_right);
	}

	void _RotateL(Node*& parent)
	{
		Node* pparent = parent->_parent;
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		if (pparent == nullptr)
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
				pparent->_left = SubR;
			else
				pparent->_right = SubR;
			SubR->_parent = pparent;
		}
		parent->_parent = SubR;
		SubR->_left = parent;
		parent->_right = SubRL;
		if (SubRL != nullptr)
			SubRL->_parent = parent;
	}

	void _RotateR(Node*& parent)
	{
		Node* pparent = parent->_parent;
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		if (pparent == nullptr)
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
				pparent->_left = SubL;
			else
				pparent->_right = SubL;
			SubL->_parent = pparent;
		}
		parent->_parent = SubL;
		SubL->_right = parent;
		parent->_left = SubLR;
		if (SubLR != nullptr)
			SubLR->_parent = parent;
	}

	Node* _root = nullptr;
};

到了这里，关于C++语法（20）---- 模拟红黑树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！