C++红黑树

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

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

一.红黑树的概念和性质

1.红黑树的概念和性质

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

2.AVL树和红黑树的区别

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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

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.共识

首先我们要达成一个共识:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
对于性质3和性质4,如果非要违反一个的话
我们选择违反性质3,而不是性质4
因为:
违反性质3还可以通过变色和旋转的方式来解决
而违法性质4的话,其他所有路径都要重新修改

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

2.新节点是黑色的坏处

插入之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
插入过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
插入之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

3.新节点是红色的好处

插入之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
插入过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
插入之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

三.红黑树的插入

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:所有红色节点的孩子不能是红色节点
这也就说明了红黑树不能存在连续的红色节点

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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

1.具体分类的说明

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
下面我们就对叔叔进行分类讨论

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

1.说明:

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

2.动图演示

插入前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
调整过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
调整之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
刚才一开始时演示的是:
cur是新增节点时的情况
但是中间过程借由祖父向上继续调整修改时,我们就已经能看出即使cur不是新增节点,调整方式和逻辑也是一模一样的!!

3.总结:

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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

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

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

1.uncle存在且为黑时:cur一定不是新增节点
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
2.为什么不能按照之前的方式只去修改颜色
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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

修改之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
修改过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
这里是对g进行右旋,动图里面刚才写错了,抱歉
修改之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
修改之后没有违反性质3

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

下面我们对照一下修改之前和修改之后,看看是否违反了性质4
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
没有违反,完美的一次修改

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

旋转之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
修改之后没有违反性质3

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

下面我们对照一下修改之前和修改之后,看看是否违反了性质4
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
完美修改

2.叔叔是祖父的左孩子

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

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

旋转之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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

旋转之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

3.叔叔不存在

C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
以右旋为例:
旋转之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
以左右双旋为例:
旋转之前:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转过程:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
旋转之后:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

4.总结:

调整颜色的总结:
C++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构

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++红黑树,数据结构与算法,爱上C++,c++,红黑树,数据结构
验证完毕

以上就是C++红黑树的全部内容,希望能对大家有所帮助!文章来源地址https://www.toymoban.com/news/detail-760680.html

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python - 深夜数据结构与算法之 AVL 树 & 红黑树

    目录 一.引言 二.高级树的简介 1.树 2.二叉树 3.二叉搜索树 4.平衡二叉树 三.AVL 树 ◆ 插入节点 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 实际操作 ◆ 总结 四.红黑树 ◆ 概念 ◆ 示例 ◆ 对比 五.总结 前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构,

    2024年01月19日
    浏览(44)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(94)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

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

    2024年02月09日
    浏览(49)
  • 数据结构 | 红黑树

    节点的左边比节点的值小,右边比节点的值大。 节点要么是 红色 ,要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候,如果不满足这些性质会

    2024年01月21日
    浏览(44)
  • [数据结构]-红黑树

    前言 作者 : 小蜗牛向前冲 名言: 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(46)
  • 【数据结构】红黑树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 在学习AVL树的时候,我们知道,当修改AVL树的结构(插入,删除)时,会通过旋转来保证平衡因子不超过1,所以频繁的修改结构会导致效率低下,今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(49)
  • 数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码(包括测试数据)   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(46)
  • 【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(44)
  • 红黑树数据结构

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的,然后很多地方也是用到红黑树,这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可

    2024年02月01日
    浏览(40)
  • 数据结构入门-11-红黑树

    史上最负盛名的平衡二叉树–红黑树,但其实就是2-3树的一种实现 也是BST,每一个节点都有颜色 性质 看 后面推导出来的结论 2-3树 :和红黑树是等价的 满足BST的基本性质,但不是一种二叉树 有两种节点: 2-3 绝对平衡:根节点到叶子节点 一定相同 2.3.1 如何维护绝对平衡

    2023年04月17日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包