【C++】:红黑树

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

朋友们、伙计们,我们又见面了,本期来给大家解读一下有关多态的知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

C 语 言 专 栏:C语言:从入门到精通

数据结构专栏:数据结构

个  人  主  页 :stackY、

C + + 专 栏   :C++

Linux 专 栏  :Linux

【C++】:红黑树,C++,c++,算法,开发语言,红黑树​ 

目录

1. 红黑树的概念

2. 红黑树的性质

3. 红黑树节点的定义 

4. 红黑树的插入

4.1 按照二叉搜索的树规则插入新节点

4.2 检测新节点插入后,红黑树的性质是否造到破坏 

情况一:uncle节点存在且为红

情况二: uncle节点不存在或者存在且为黑

1. p为g的左,且cur为p的左或者p为g的右,且cur为p的右

2. p为g的左,且cur为p的右或者p为g的右,且cur为p的左

5. 红黑树的验证

6. 红黑树的其他接口

7. 红黑树与AVL树的比较

8. 完整代码 


1. 红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。【C++】:红黑树,C++,c++,算法,开发语言,红黑树

2. 红黑树的性质

  • 1. 每个结点不是红色就是黑色
  • 2. 根节点是黑色的
  • 3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  • 4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
  • 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

3. 红黑树节点的定义 

红黑树节点的定义我们使用pair进行数据的存储,那么这里就存在一个问题,构造出来的节点默认是什么颜色呢?

根据红黑树的性质,每一条路径中黑色节点的数量必须相等,如果构造出来的节点默认设置为黑,那么在一条路径中插入一个黑色节点,为了维持红黑树的规则就需要在别的路径中也加上黑色节点,这样子做的话代价比较大,所以我们将构造出来的节点的颜色默认置为红色,这样子插入一个红色的节点对其他的路径并没有什么影响。

//红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, T>* _left;    //左子树节点
	RBTreeNode<K, T>* _right;   //右子树节点
	RBTreeNode<K, T>* _parent;  //父节点
	Color _col;                 //节点颜色
	pair<K, V> _kv;             //节点的数据

	//节点的构造
	RBTreeNode(const pair<K, T>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
		,_kv(kv)
	{}
};

4. 红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

4.1 按照二叉搜索的树规则插入新节点  

//插入
	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 (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->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//...
		
		return true;
	}

4.2 检测新节点插入后,红黑树的性质是否造到破坏 

因为新节点的默认颜色是红色,因此:如果其父亲节点的颜色是黑色,没有违反红黑树任何
性质,则不需要调整;但当新插入节点的父亲节点颜色为红色时,就违反了不能有连在一起的红色节点,此时需要对红黑树分情况处理:

首先我们要了解一下红黑树的基本情况:

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

cur(c):代表当前节点

parent(p):代表cur的父亲节点

uncle(u):代表cur的叔叔节点

grandfather(g):代表当前节点的祖父节点

情况一:uncle节点存在且为红

注意:这里显示的红黑树有可能是一棵完整的红黑树,也有可能是一棵子树。

这里有三个节点是已知情况,因为插入的默认节点颜色是红色,插入红色时是需要进行调整的,所以cur和parent是红色,那么grandfather节点必定是黑色。
【C++】:红黑树,C++,c++,算法,开发语言,红黑树

如果叔叔节点存在且为红色,那么只需要进行简单的变色即可,将parent和uncle变为黑色,这时这个子树的每一个路径下的黑色节点就多了一个,因此还需要将grandfather节点变为红色,这样就使它的每一个路径少了一个黑色节点,这样才能平衡多出的黑色节点。

改变完颜色之后,由于我们不确定grandfather节点是否还有父亲节点,如果它的父亲节点为黑色,那么则不需要处理,如果它的父亲为红色节点,那么还需要继续向上处理,为了方便,我们可以将grandfather继续当作cur,继续向上调整。

综上所述:当uncle节点存在且为红色节点时,将parent和uncle改为黑色,然后将grandfather改为红色,再将grandfather继续当作新的cur,继续向上调整。

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

如果这里已经是一棵完整的红黑树了,此时的cur就变成了根节点,但是它被改成了红色,所以就需要再将根节点置为黑色。

代码实现:

//插入
	bool Insert(const pair<K, V>& kv)
	{
		//和搜索二叉插入同样的逻辑
        //...

		//判断节点的颜色,是否破坏了平衡
		while (parent && parent->_col == RED)
		{
			//祖父节点
			Node* grandfather = parent->_parent;
			//判断父亲与叔叔的位置
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//其他情况
				//...
			}
			else
			{
				Node* uncle = grandfather->_left;
				//叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//其他情况
				//...
			}
		}
        //将根节点再次置黑保持红黑树的平衡
        _root->_col = BLACK;
	}

情况二: uncle节点不存在或者存在且为黑

这里还需要分了两种情况:

1. p为g的左,且cur为p的左或者p为g的右,且cur为p的右

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

这种情况如果只通过单纯的变色是不能达到效果的,需要配合旋转才能达到红黑树的平衡。

①如果parent为grandfather的左,且cur为parent的左

这种情况需要先以p为根节点进行右单旋,然后进行变色,需要将parent和grandfather变色,将parent变为黑色,将grandfather变为红色。

②如果parent为grandfather的右,且cur为parent的右

这种情况需要先以p为根节点进行左单旋,然后进行变色,需要将parent和grandfather变色,将parent变为黑色,将grandfather变为红色。

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

2. p为g的左,且cur为p的右或者p为g的右,且cur为p的左

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

这种情况类似于AVL树中的双旋,通过单旋+变色是不能达到红黑树的平衡的,需要经过两次旋转,再加变色才可以达到红黑树的平衡。

①如果parent为grandfather的左,且cur为parent的右

先以parent为根进行左旋,然后再以grandfather为根进行右旋,然后将cur变黑,将grandfater变红。

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

②如果parent为grandfather的右,且cur为parent的左

先以parent为根进行右旋,然后再以grandfather为根进行左旋,然后将cur变黑,将grandfather变红。

【C++】:红黑树,C++,c++,算法,开发语言,红黑树

如果我们仔细观察,不难发现,在上述的两者双旋情况中,在旋转一次之后得到的红黑树和和1中的情况是一样的,那么也就说明了不一定cur是新插入的节点,还有可能是下面的子树在调整完之后将cur变为了红节点,然后导致红黑树的不平衡。

代码演示:

左单旋和右单旋就不做过多解释了,AVL树部分有详细的介绍。

//插入
	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 (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->_right = cur;
			cur->_parent = parent;
		}
		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 = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //叔叔节点不存在或者存在且为黑
				{
					if (cur == parent->_left)   //该路径的parent已经是grandfather的左
					{
						//旋转+变色
						Rotate_right(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else                       //cur是parent的右
					{
						//双旋+变色
						Rotate_left(parent);
						Rotate_right(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else //parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				//叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)   //该路径的parent已经是grandfather的右
					{
						//旋转+变色
						Rotate_left(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else                        //cur是parent的左
					{
						Rotate_right(parent);
						Rotate_left(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		//将根节点再次置黑保持红黑树的平衡
		_root->_col = BLACK;
		
		return true;
	}

5. 红黑树的验证

红黑树的检测分为两步:

  • 1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  • 2. 检测其是否满足红黑树的性质

中序遍历比较简单,就不做赘述了,主要来看一下第二条:

首先红黑树的性质:

  • 1. 每个结点不是红色就是黑色
  • 2. 根节点是黑色的
  • 3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  • 4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点

①因为我们对颜色使用的是枚举,所以每个节点不是红色就是黑色。

②根节点是否为黑色只需要对_root的_col判断是否为黑色即可。

③判断是否存在连续的红色节点可以通过判断一个节点的父亲节点是否为红色即可。

④判断每条路径是否具有相同的黑色节点可以封装一个函数,然后传递一个路径中黑色节点的个数作为基准值,通过判断剩余路径黑色节点的个数与这个基准值相不相等即可。求每条路径的个数可以采用深度优先遍历找到黑色节点计数器++即可。

代码演示:

//判断是否平衡
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		//1.判断根是否为黑
		if (_root->_col == RED)
			return false;

		int standard_val = 0;  	//最左路径的黑色节点个数
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				standard_val++;
			cur = cur->_left;
		}
		int Black_size = 0;
		return Check(_root,standard_val,Black_size);
	}
private:
	//判断是否平衡
	bool Check(Node* root, const int standard_val, int Black_size)
	{
		if (root == nullptr)
		{
			if (Black_size != standard_val)   //比较黑色节点的个数
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			else
				return true;
		}
		//判断它与它父亲的颜色
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;

			return false;
		}
		//黑色节点计数器++
		if (root->_col == BLACK)
		{
			Black_size++;
		}
		//递归它的左右子树
		return Check(root->_left, standard_val, Black_size)
			&& Check(root->_right, standard_val, Black_size);
	}

6. 红黑树的其他接口

红黑树的查找、节点个数、树的高度

	//高度
	int Height()
	{
		return _Height(_root);
	}
	//节点个数
	size_t Size()
	{
		return _Size(_root);
	}
	//查找
	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 NULL;
	}
private:
	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;

		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

7. 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是,红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。

8. 完整代码 

#pragma once

//枚举定义节点颜色
enum Color 
{
	RED,    //红色
	BLACK   //黑色
};

//红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;    //左子树节点
	RBTreeNode<K, V>* _right;   //右子树节点
	RBTreeNode<K, V>* _parent;  //父节点
	Color _col;                 //节点颜色
	pair<K, V> _kv;             //节点的数据

	//节点的构造
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
		,_kv(kv)
	{}
};

//红黑树的实现
template<class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	//插入
	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 (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->_right = cur;
			cur->_parent = parent;
		}
		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 = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //叔叔节点不存在或者存在且为黑
				{
					if (cur == parent->_left)   //该路径的parent已经是grandfather的左
					{
						//旋转+变色
						Rotate_right(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else                       //cur是parent的右
					{
						//双旋+变色
						Rotate_left(parent);
						Rotate_right(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else //parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				//叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//将grandfather变为新的cur继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)   //该路径的parent已经是grandfather的右
					{
						//旋转+变色
						Rotate_left(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else                        //cur是parent的左
					{
						Rotate_right(parent);
						Rotate_left(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		//将根节点再次置黑保持红黑树的平衡
		_root->_col = BLACK;
		return true;
	}

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//判断是否平衡
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		//1.判断根是否为黑
		if (_root->_col == RED)
			return false;

		int standard_val = 0;  	//最左路径的黑色节点个数
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				standard_val++;
			cur = cur->_left;
		}
		int Black_size = 0;
		return Check(_root,standard_val,Black_size);
	}
	//高度
	int Height()
	{
		return _Height(_root);
	}
	//节点个数
	size_t Size()
	{
		return _Size(_root);
	}
	//查找
	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 NULL;
	}
private:
	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;

		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	//判断是否平衡
	bool Check(Node* root, const int standard_val, int Black_size)
	{
		if (root == nullptr)
		{
			if (Black_size != standard_val)   //比较黑色节点的个数
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			else
				return true;
		}
		//判断它与它父亲的颜色
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;

			return false;
		}
		//黑色节点计数器++
		if (root->_col == BLACK)
		{
			Black_size++;
		}
		//递归它的左右子树
		return Check(root->_left, standard_val, Black_size)
			&& Check(root->_right, standard_val, Black_size);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
	//右单旋
	void Rotate_right(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;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
				subL->_parent = ppNode;
			}
			else
			{
				ppNode->_right = subL;
				subL->_parent = ppNode;
			}
		}
	}

	//左单旋
	void Rotate_left(Node* parent)
	{
		Node* subR = parent->_right;  
		Node* subRL = subR->_left; 
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
	}
private:
	Node* _root = nullptr;
};

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,欲知后事如何,请听下回分解~,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!   文章来源地址https://www.toymoban.com/news/detail-755961.html

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

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

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

相关文章

  • C++ 红黑树

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

    2024年02月05日
    浏览(42)
  • 【C++】实现红黑树

    红黑树是一个二叉搜索树,与AVL树相比,红黑树不再使用平衡因子来控制树的左右子树高度差,而是用颜色来控制平衡,颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色,就可以确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树的规

    2024年03月25日
    浏览(42)
  • C++红黑树

    前置说明: 需要学习AVL树的旋转之后再来看红黑树的旋转 因为红黑树的旋转是复用的AVL树的旋转的: 大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转 C++ AVL树(四种旋转,插入) 对于颜色我们采用枚举类型定义 对于红黑树节点,依旧采用Key-Value模型存储pair 1.共识 首先我们

    2024年02月04日
    浏览(40)
  • C++手撕红黑树

    概念 和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black 红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态 所以说红黑树并不

    2024年04月12日
    浏览(45)
  • 【C++】红黑树

    正文开始前给大家推荐个网站,前些天发现了一个巨牛的 人工智能 学习网站, 通俗易懂,风趣幽默 ,忍不住分享一下给大家。 点击跳转到网站。 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的

    2024年01月16日
    浏览(49)
  • C++ 实现红黑树

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

    2024年02月05日
    浏览(42)
  • C++中的红黑树

    搜索二叉树的概念:二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 简单

    2024年02月09日
    浏览(47)
  • C++【红黑树】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 红黑树是平衡二叉搜索树中的一种,红黑树性能优异,广泛用于实践中,比如 Linux 内核中的 CFS 调度器就用到了红黑树,由此可见红黑树的重要性。红黑树在实现时仅仅依靠 红 与 黑 两

    2024年02月10日
    浏览(35)
  • 【C++】手撕红黑树

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:能直接手撕红黑树。 毒鸡汤:行到水穷处,坐看云起时。。 望小伙伴们点赞👍收藏✨加关注哟💕💕  相信大家肯定听过在C++大名鼎鼎的两颗树,这两颗树分别

    2024年03月23日
    浏览(39)
  • 【C++】红黑树插入删除

    喜欢的点赞,收藏,关注一下把! 红黑树 ,是一种 二叉搜索树 ,但 在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制 , 红黑树确保没有一条路径会比其他路径长出俩倍 ,因而是 接近平衡 的。

    2024年02月02日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包