1. AI技术聚合首页
  2. IT

C++红黑树

xiaoxingxing • • IT • 阅读 67

C++红黑树

  • 一.红黑树的概念和性质
    • 1.红黑树的概念和性质
    • 2.AVL树和红黑树的区别
  • 二.我们要实现的大致框架
    • 1.红黑树节点的定义
    • 2.为什么新节点默认是红色?
      • 1.共识
      • 2.新节点是黑色的坏处
      • 3.新节点是红色的好处
  • 三.红黑树的插入
  • 1.插入逻辑跟BST相同的那一部分
  • 2.分类讨论插入逻辑
    • 1.新插入节点的父亲是黑色
    • 2.新插入节点的父亲是红色
      • 1.具体分类的说明
      • 2.新插入节点的叔叔存在是红色
        • 1.说明:
        • 2.动图演示
        • 3.总结:
      • 3.新插入节点的叔叔不存在或者存在是黑色
        • 1.叔叔是祖父的右孩子
          • 1.说明
          • 2.旋转方案
            • 1.cur是parent的左孩子(右旋)
            • 2.cur是parent的右孩子(左右双旋)
        • 2.叔叔是祖父的左孩子
          • 1.cur是parent的右孩子(左旋)
          • 2.cur是parent的左孩子(右左双旋)
        • 3.叔叔不存在
        • 4.总结:
  • 3.插入代码
  • 四.红黑树的验证
  • 五.完整代码

前置说明:
需要学习AVL树的旋转之后再来看红黑树的旋转
因为红黑树的旋转是复用的AVL树的旋转的:
大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转
C++ AVL树(四种旋转,插入)

一.红黑树的概念和性质

1.红黑树的概念和性质

2.AVL树和红黑树的区别

二.我们要实现的大致框架

1.红黑树节点的定义

对于颜色我们采用枚举类型定义
对于红黑树节点,依旧采用Key-Value模型存储pair

enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _pLeft;
	RBTreeNode<K,V>* _pRight;
	RBTreeNode<K,V>* _pParent;
	Color _color;
	pair<K,V> _data;
	//新插入的节点默认是红色
	RBTreeNode(const pair<K,V>& data)
		:_pLeft(nullptr)
		,_pRight(nullptr)
		,_pParent(nullptr)
		,_color(RED)
		,_data(data)
	{}
};

2.为什么新节点默认是红色?

1.共识

首先我们要达成一个共识:

对于性质3和性质4,如果非要违反一个的话
我们选择违反性质3,而不是性质4
因为:
违反性质3还可以通过变色和旋转的方式来解决
而违法性质4的话,其他所有路径都要重新修改

因此违法性质3的损失更小,调整更简单
违法性质4…后果不言而喻…

2.新节点是黑色的坏处

插入之前:

插入过程:
在这里插入图片描述
插入之后:

3.新节点是红色的好处

插入之前:

插入过程:
在这里插入图片描述
插入之后:

三.红黑树的插入

1.插入逻辑跟BST相同的那一部分

下面是跟BST普通二叉搜索树的插入逻辑相同的那部分
唯一不太相同的是把根节点的颜色改成黑色了而已

bool Insert(const pair<K,V>& data)
{
	if (_pRoot == nullptr)
	{
		_pRoot = new Node(data);
		//根节点是黑色
		_pRoot->_color = BLACK;
		return true;
	}
	Node* cur = _pRoot, * parent = nullptr;
	while (cur)
	{
		//比我小,往左找
		if (data.first < cur->_data.first)
		{
			parent = cur;
			cur = cur->_pLeft;
		}
		//比我大,往右找
		else if (data.first > cur->_data.first)
		{
			parent = cur;
			cur = cur->_pRight;
		}
		//有重复元素,插入失败
		else
		{
			return false;
		}
	}
	//找到空位置,开始插入
	cur = new Node(data);
	//连接父亲和孩子
	if (cur->_data.first < parent->_data.first)
	{
		parent->_pLeft = cur;
	}
	else
	{
		parent->_pRight = cur;
	}
	cur->_pParent = parent;
	//开始讨论节点颜色问题
	//.....
	return true;
}

2.分类讨论插入逻辑

介绍了新插入的节点必须是红色之后
我们就可以分情况讨论了

1.新插入节点的父亲是黑色

因为红黑树的性质3:所有红色节点的孩子不能是红色节点
这也就说明了红黑树不能存在连续的红色节点

2.新插入节点的父亲是红色

1.具体分类的说明

在这里插入图片描述
下面我们就对叔叔进行分类讨论

2.新插入节点的叔叔存在是红色

1.说明:

这里以叔叔是祖父的右孩子为例演示
其实叔叔是祖父的左孩子的话是一模一样的,就不再赘述了

2.动图演示

插入前:

调整过程:
在这里插入图片描述
调整之后:

刚才一开始时演示的是:
cur是新增节点时的情况
但是中间过程借由祖父向上继续调整修改时,我们就已经能看出即使cur不是新增节点,调整方式和逻辑也是一模一样的!!

3.总结:

3.新插入节点的叔叔不存在或者存在是黑色

刚才的那种情况只需要变色即可
现在就需要旋转+变色了
跟AVL树的旋转类似,依然是分为4种情况
依然是画抽象图来理解
画图里面规定:
p:代表parent,父亲
c:代表cur,孩子
g:grandParent,祖父
u:uncle,叔叔
a,b,c,d,e代表红黑树或者空节点
ar:ancestor:祖父的父亲

1.叔叔是祖父的右孩子
1.说明

1.uncle存在且为黑时:cur一定不是新增节点

2.为什么不能按照之前的方式只去修改颜色

2.旋转方案
1.cur是parent的左孩子(右旋)

修改之前:

修改过程:
在这里插入图片描述
这里是对g进行右旋,动图里面刚才写错了,抱歉
修改之后:

修改之后没有违反性质3

注意:因为此时祖父变成了p,而且p是黑色,所以就不会继续往上修改了,证明修改完毕

下面我们对照一下修改之前和修改之后,看看是否违反了性质4

没有违反,完美的一次修改

2.cur是parent的右孩子(左右双旋)

旋转之前:

旋转过程:
在这里插入图片描述
旋转之后:

修改之后没有违反性质3

注意:因为此时祖父变成了c而且c是黑色,所以无需继续往上修改了
但是因为此时p是红色,会继续进入循环,这样就会发生一些意想不到的错误,所以此时必须break

下面我们对照一下修改之前和修改之后,看看是否违反了性质4

完美修改

2.叔叔是祖父的左孩子

跟叔叔是祖父的右孩子就特别像了,直接给动图了

1.cur是parent的右孩子(左旋)

旋转之前:

旋转过程:
在这里插入图片描述
旋转之后:

2.cur是parent的左孩子(右左双旋)

旋转之前:

旋转过程:
在这里插入图片描述
旋转之后:

3.叔叔不存在


以右旋为例:
旋转之前:

旋转过程:

旋转之后:

以左右双旋为例:
旋转之前:

旋转过程:

旋转之后:

4.总结:

调整颜色的总结:

3.插入代码

// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
// 注意：为了简单起见，本次实现红黑树不存储重复性元素
bool Insert(const pair<K,V>& data)
{
	if (_pRoot == nullptr)
	{
		_pRoot = new Node(data);
		//根节点是黑色
		_pRoot->_color = BLACK;
		return true;
	}
	Node* cur = _pRoot, * parent = nullptr;
	while (cur)
	{
		//比我小,往左找
		if (data.first < cur->_data.first)
		{
			parent = cur;
			cur = cur->_pLeft;
		}
		//比我大,往右找
		else if (data.first > cur->_data.first)
		{
			parent = cur;
			cur = cur->_pRight;
		}
		//有重复元素,插入失败
		else
		{
			return false;
		}
	}
	//找到空位置,开始插入
	cur = new Node(data);
	//连接父亲和孩子
	if (cur->_data.first < parent->_data.first)
	{
		parent->_pLeft = cur;
	}
	else
	{
		parent->_pRight = cur;
	}
	cur->_pParent = parent;
	//父亲是黑色,插入成功
	if (parent->_color == BLACK)
	{
		return true;
	}
	//父亲是红色,需要调整
	//且此时爷爷一定是黑色
	//根据叔叔的颜色来调整
	while (parent && parent->_color == RED)
	{
		Node* grandParent = parent->_pParent;
		//爸爸是爷爷的左孩子
		if (parent == grandParent->_pLeft)
		{
			Node* uncle = grandParent->_pRight;
			//根据叔叔的颜色来调整
			//1.叔叔存在且为红
			if (uncle && uncle->_color == RED)
			{
				//修改爸爸,叔叔,爷爷的颜色
				uncle->_color = parent->_color = BLACK;
				grandParent->_color = RED;
				//此时视爷爷为新插入的红色节点继续向上影响
				cur = grandParent;
				parent = cur->_pParent;
			}
			//2.叔叔不存在或者叔叔是黑
			else
			{
				//1.我是爸爸的左孩子
				if (parent->_pLeft == cur)
				{
					//对爷爷进行一次右旋
					RotateR(grandParent);
					//把爷爷改成红色,爸爸改成黑色
					grandParent->_color = RED;
					parent->_color = BLACK;
					//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
				}
				//2.我是爸爸的右孩子
				else
				{
					//1.对爸爸进行左旋
					RotateL(parent);
					//2.对爷爷右旋
					RotateR(grandParent);
					//3.孩子改成黑色,爷爷改成红色
					cur->_color = BLACK;
					grandParent->_color = RED;
					//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
					break;
				}
			}
		}
		//爸爸是爷爷的右孩子
		else
		{
			Node* uncle = grandParent->_pLeft;
			//1.叔叔存在且为红
			if (uncle && uncle->_color == RED)
			{
				uncle->_color = parent->_color = BLACK;
				grandParent->_color = RED;
				cur = grandParent;
				parent = cur->_pParent;
			}
			//2.叔叔不存在或者叔叔为黑
			else
			{
				//1.我是爸爸的右孩子
				if (parent->_pRight == cur)
				{
					//对爷爷左旋
					RotateL(grandParent);
					//爷爷改成红色,爸爸改成黑色
					grandParent->_color = RED;
					parent->_color = BLACK;
					//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
				}
				//2.我是爸爸的左孩子
				else
				{
					//1.对爸爸右旋
					RotateR(parent);
					//2.对爷爷左旋
					RotateL(grandParent);
					//3.把孩子改成黑色,爷爷改成红色
					cur->_color = BLACK;
					grandParent->_color = RED;
					//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
					break;
				}
			}
		}
	}
	_pRoot->_color = BLACK;
	return true;
}

四.红黑树的验证

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:
	// 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const K& key)
	{
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data.first > key)
			{
				cur = cur->_pLeft;
			}
			else if (cur->_data.second < key)
			{
				cur = cur->_pRight;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		//1.空树是红黑树
		if (_pRoot == nullptr)
		{
			return true;
		}
		//2.根节点不能为红色
		if (_pRoot->_color == RED)
		{
			return false;
		}
		//3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同   找参考值
		size_t ReferenceCount = 0;
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_color == BLACK)
			{
				ReferenceCount++;
			}
			cur = cur->_pLeft;
		}
		return _IsValidRBTRee(_pRoot, 0, ReferenceCount);
	}


private:
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount)
	{
		if (pRoot == nullptr)
		{
			if (blackCount != ReferenceCount)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		//验证性质: 红黑树中不能存在连续的红色节点
		//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲
		//只需要保证红色节点的父亲不是红色节点即可
		if (pRoot->_color == RED)
		{
			if (pRoot->_pParent->_color == RED)
			{
				cout << "存在连续的红色节点" << endl;
				return false;
			}
		}
		else
		{
			blackCount++;
		}
		return _IsValidRBTRee(pRoot->_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot->_pRight, blackCount, ReferenceCount);
	}
	
private:
	Node* _pRoot = nullptr;
};

五.完整代码

1.RBTree.h

#pragma once
enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _pLeft;
	RBTreeNode<K,V>* _pRight;
	RBTreeNode<K,V>* _pParent;
	Color _color;
	pair<K,V> _data;
	//新插入的节点默认是红色
	RBTreeNode(const pair<K,V>& data)
		:_pLeft(nullptr)
		,_pRight(nullptr)
		,_pParent(nullptr)
		,_color(RED)
		,_data(data)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const pair<K,V>& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			//根节点是黑色
			_pRoot->_color = BLACK;
			return true;
		}
		Node* cur = _pRoot, * parent = nullptr;
		while (cur)
		{
			//比我小,往左找
			if (data.first < cur->_data.first)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			//比我大,往右找
			else if (data.first > cur->_data.first)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			//有重复元素,插入失败
			else
			{
				return false;
			}
		}
		//找到空位置,开始插入
		cur = new Node(data);
		//连接父亲和孩子
		if (cur->_data.first < parent->_data.first)
		{
			parent->_pLeft = cur;
		}
		else
		{
			parent->_pRight = cur;
		}
		cur->_pParent = parent;
		//父亲是黑色,插入成功
		if (parent->_color == BLACK)
		{
			return true;
		}
		//父亲是红色,需要调整
		//且此时爷爷一定是黑色
		//根据叔叔的颜色来调整
		while (parent && parent->_color == RED)
		{
			Node* grandParent = parent->_pParent;
			//爸爸是爷爷的左孩子
			if (parent == grandParent->_pLeft)
			{
				Node* uncle = grandParent->_pRight;
				//根据叔叔的颜色来调整
				//1.叔叔存在且为红
				if (uncle && uncle->_color == RED)
				{
					//修改爸爸,叔叔,爷爷的颜色
					uncle->_color = parent->_color = BLACK;
					grandParent->_color = RED;
					//此时视爷爷为新插入的红色节点继续向上影响
					cur = grandParent;
					parent = cur->_pParent;
				}
				//2.叔叔不存在或者叔叔是黑
				else
				{
					//1.我是爸爸的左孩子
					if (parent->_pLeft == cur)
					{
						//对爷爷进行一次右旋
						RotateR(grandParent);
						//把爷爷改成红色,爸爸改成黑色
						grandParent->_color = RED;
						parent->_color = BLACK;
						//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
					}
					//2.我是爸爸的右孩子
					else
					{
						//1.对爸爸进行左旋
						RotateL(parent);
						//2.对爷爷右旋
						RotateR(grandParent);
						//3.孩子改成黑色,爷爷改成红色
						cur->_color = BLACK;
						grandParent->_color = RED;
						//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
						break;
					}
				}
			}
			//爸爸是爷爷的右孩子
			else
			{
				Node* uncle = grandParent->_pLeft;
				//1.叔叔存在且为红
				if (uncle && uncle->_color == RED)
				{
					uncle->_color = parent->_color = BLACK;
					grandParent->_color = RED;
					cur = grandParent;
					parent = cur->_pParent;
				}
				//2.叔叔不存在或者叔叔为黑
				else
				{
					//1.我是爸爸的右孩子
					if (parent->_pRight == cur)
					{
						//对爷爷左旋
						RotateL(grandParent);
						//爷爷改成红色,爸爸改成黑色
						grandParent->_color = RED;
						parent->_color = BLACK;
						//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
					}
					//2.我是爸爸的左孩子
					else
					{
						//1.对爸爸右旋
						RotateR(parent);
						//2.对爷爷左旋
						RotateL(grandParent);
						//3.把孩子改成黑色,爷爷改成红色
						cur->_color = BLACK;
						grandParent->_color = RED;
						//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
						break;
					}
				}
			}
		}
		_pRoot->_color = BLACK;
		return true;
	}

	// 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const K& key)
	{
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data.first > key)
			{
				cur = cur->_pLeft;
			}
			else if (cur->_data.second < key)
			{
				cur = cur->_pRight;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		//1.空树是红黑树
		if (_pRoot == nullptr)
		{
			return true;
		}
		//2.根节点不能为红色
		if (_pRoot->_color == RED)
		{
			return false;
		}
		//3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同   找参考值
		size_t ReferenceCount = 0;
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_color == BLACK)
			{
				ReferenceCount++;
			}
			cur = cur->_pLeft;
		}
		return _IsValidRBTRee(_pRoot, 0, ReferenceCount);
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}
private:
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount)
	{
		if (pRoot == nullptr)
		{
			if (blackCount != ReferenceCount)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		//验证性质: 红黑树中不能存在连续的红色节点
		//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲
		//只需要保证红色节点的父亲不是红色节点即可
		if (pRoot->_color == RED)
		{
			if (pRoot->_pParent->_color == RED)
			{
				cout << "存在连续的红色节点" << endl;
				return false;
			}
		}
		else
		{
			blackCount++;
		}
		return _IsValidRBTRee(pRoot->_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot->_pRight, blackCount, ReferenceCount);
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		Node* grandParent = pParent->_pParent;
		subL->_pRight = pParent;
		pParent->_pParent = subL;
		pParent->_pLeft = subLR;
		if (subLR)
			subLR->_pParent = pParent;
		if (grandParent == nullptr)
		{
			_pRoot = subL;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subL;
			}
			else
			{
				grandParent->_pRight = subL;
			}
			subL->_pParent = grandParent;
		}
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		Node* grandParent = pParent->_pParent;
		pParent->_pParent = subR;
		subR->_pLeft = pParent;
		pParent->_pRight = subRL;
		if (subRL)
			subRL->_pParent = pParent;
		//说明此时pParent是_pRoot
		if (grandParent == nullptr)
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		//说明此时pParent所在的树是一颗子树,需要跟父亲链接
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subR;
			}
			else
			{
				grandParent->_pRight = subR;
			}
			subR->_pParent = grandParent;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr) return;
		_InOrder(root->_pLeft);
		cout << root->_data.first << " " << root->_data.second << " ";
		_InOrder(root->_pRight);
	}
private:
	Node* _pRoot = nullptr;
};

2.test.cpp

#include <iostream>
using namespace std;
#include <assert.h>
#include "RBtree1.h"
#include <vector>
void test1()
{
	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> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << endl;
	cout << t.IsValidRBTRee() << endl;

}
void test2()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << t.IsValidRBTRee() << endl;
}

int main()
{
	test2();
	return 0;
}


验证完毕

以上就是C++红黑树的全部内容,希望能对大家有所帮助!

版权声明：本文为博主作者：program-learner原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/Wzs040810/article/details/135121599

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月29日
下一篇 2023年12月29日

相关推荐